|
一维dp
53. 最大子序和（子序要求连续）
状态定义：dp[i] 以第?i个数结尾的「连续子数组的最大和」。（1个循环）
状态方程：dp[i] = max(nums[i], dp[i-1]+nums[i])
300. 最长递增子序列（子序列不要求连续）
状态定义：dp[i]?的值代表?nums?前?i?个数字的最长子序列长度。（2个循环）
状态方程：dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/
二维dp
64.最小路径和?
状态定义：设 dp?为大小 m×n?矩阵，其中?dp[i][j]?的值代表直到走到 (i,j)?的最小路径和。
状态方程：grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
https://leetcode-cn.com/problems/minimum-path-sum/solution/zui-xiao-lu-jing-he-dong-tai-gui-hua-gui-fan-liu-c/
|