（前面的分治还没补完，只能勉强打卡，有空把详细代码注释和思路给补了）
动态规划
动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
例题
5. 最长回文子串
原题传送：链接
其他解法：【题解】【LeetCode】5. 最长回文子串
给定一个字符串 s，找到 s中最长的回文子串。你可以假设 s的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
思路：
动态规划。
Python:
class Solution:def longestPalindrome(self, s: str) -> str:dp = [[False] * len(s) for _ in range(len(s))]res = ""for l in range(len(s)): # 枚举子串的长度 l+1for i in range(len(s)): # 枚举子串的起始位置 i，结束位置为j=i+lj = i + lif j >= len(s):breakif l == 0:dp[i][j] = Trueelif l == 1:dp[i][j] = (s[i] == s[j])else:dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])if dp[i][j] and l + 1 > len(res):res = s[i:j+1]return res
72. 编辑距离
原题传送：链接
其他解法：【题解】【LeetCode】72. 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2:
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
思路：
动态规划。分增删改三种情况讨论。
Python:
class Solution:def minDistance(self, word1: str, word2: str) -> int:n, m = len(word1), len(word2)dp = [ [0] * (m + 1) for _ in range(n + 1)]word1 = " " + word1word2 = " " + word2# 边界状态初始化for i in range(n + 1):dp[i][0] = ifor j in range(m + 1):dp[0][j] = j# 计算所有 DP 值for i in range(1, n+1):for j in range(1, m+1):dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1t = 1 if word1[i] != word2[j] else 0dp[i][j] = min(dp[i][j], dp[i-1][j-1]+t)return dp[n][m]
198. 打家劫舍
原题传送：链接
其他解法：【题解】【LeetCode】198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1:
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
0 <= nums.length <= 1000 <= nums[i] <= 400
思路：
动态规划。
Python:
class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)f, g = [0 for _ in range(n+1)], [0 for _ in range(n+1)]for i in range(1, n+1):f[i] = g[i-1] + nums[i-1]g[i] = max(f[i-1], g[i-1])return max(f[n], g[n])
213. 打家劫舍 II
原题传送：链接
其他解法：【题解】【LeetCode】213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。
思路：
动态规划。
Python:
class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n == 0:return 0if n == 1:return nums[0]f, g = [0 for _ in range(n+1)], [0 for _ in range(n+1)]for i in range(2, n+1):f[i] = g[i-1] + nums[i-1]g[i] = max(f[i-1], g[i-1])ans = max(f[n], g[n])f[1] = nums[0]g[1] = 0for i in range(2, n+1):f[i] = g[i-1] + nums[i-1]g[i] = max(f[i-1], g[i-1])return max(ans, g[n])
516. 最长回文子序列
原题传送：链接
其他解法：【题解】【LeetCode】516. 最长回文子序列
给定一个字符串 s，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s的最大长度为 1000。
示例 1:
输入: "bbbab"
输出: 4
一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入: "cbbd"
输出: 2
一个可能的最长回文子序列为 "bb"。
提示：
1 <= s.length <= 1000s只包含小写英文字母
思路：
动态规划。
Python:
class Solution:def longestPalindromeSubseq(self, s: str) -> int:n = len(s)dp = [[0] * n for _ in range(n)]for i in range(n):dp[i][i] = 1for j in range(i-1, -1, -1):if s[j] == s[i]:dp[j][i] = 2 + dp[j + 1][i - 1]else:dp[j][i] = max(dp[j + 1][i], dp[j][i - 1])return dp[0][n - 1]
674. 最长连续递增序列
原题传送：链接
其他解法：【题解】【LeetCode】674. 最长连续递增序列
给定一个未经排序的整数数组，找到最长且连续的递增序列，并返回该序列的长度。
示例 1:
输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。
示例 2:
输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。
注意： 数组长度不会超过10000。
思路：
遍历，递增当前长度+1，非递增当前长度和最大值比较，更新最大值并将当前长度置1。
Python:
class Solution:def findLengthOfLCIS(self, nums: List[int]) -> int:l = 1ans = 0 if len(nums) == 0 else 1for i in range(1, len(nums)):if nums[i] > nums[i-1]:l += 1else:l = 1if l > ans:ans = lreturn ans
参考文章
- 第16期 Datawhale 组队学习活动
- Datawhale课程——动态规划
- 动态规划-维基百科