动态规划

LeetCode 198 https://leetcode.cn/problems/house-robber/description/ 难度：中等 状态转移： f[i + 2] = max(f[i + 1], f[i] + nums[i]); 时间复杂度：O(n)。其中 n 为 nums 的长度。 空间复杂度：O(n)。 ...

LeetCode 152 https://leetcode.cn/problems/maximum-product-subarray/description/ 难度：中等 动态规划，类似 LeetCode 53 最大子数组和。由于负负得正，需要维护以 i 结尾的连续子数组乘积的最大值和最小值。 f_max[i] = max({f_max[i - 1] * x, f_min[i - 1] * x, x}); f_min[i] = min({f_max[i - 1] * x, f_min[i - 1] * x, x}); 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(n)。 ...

LeetCode 62 https://leetcode.cn/problems/unique-paths/description/ 难度：中等 基础的网格图 DP。 时间复杂度：O(mn)。 空间复杂度：O(mn)。 ...

LeetCode 122 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/ 难度：中等 买卖股票类题目一般都是状态机 DP。f[i][0] 不持有股票，f[i][1] 持有股票。答案是 f[n][0]。初始化 f[0][0] = 0，f[0][1] = INT_MIN。 注意二维的 DP 数组，vector<int[2]> f(n + 1) 会比 vector<vector> 更快，如果数组长度固定，尽量使用 array 而不是 vector。 时间复杂度：O(n)，其中 n 为 prices 的长度。 空间复杂度：O(n)。 ...

LeetCode 221 https://leetcode.cn/problems/maximal-square/description/ 难度：中等 二维 DP，状态转移方程如下，并在计算 f 数组的时候维护正方形边长的最大值。 f[i + 1][j + 1] = min({f[i + 1][j], f[i][j + 1], f[i][j]}) + 1; 时间复杂度：O(mn)，其中 m 和 n 是矩阵的行数和列数。需要遍历原始矩阵中的每个元素计算 dp 的值。 空间复杂度：O(mn)，其中 m 和 n 是矩阵的行数和列数。创建了一个和原始矩阵大小相同的矩阵 dp。由于状态转移方程中的 dp(i,j) 由其上方、左方和左上方的三个相邻位置的 dp 值决定，因此可以使用两个一维数组进行状态转移，空间复杂度优化至 O(n)。 ...

LeetCode 543 https://leetcode.cn/problems/diameter-of-binary-tree/description/ 难度：简单 树形 DP 中的直径 DP。 链：从子树中的叶子节点到当前节点的路径。把最长链的长度，作为 dfs 的返回值。根据这一定义，空节点的链长是 −1，叶子节点的链长是 0。 直径：等价于由两条（或者一条）链拼成的路径。我们枚举每个 node，假设直径在这里「拐弯」，也就是计算由左右两条从下面的叶子节点到 node 的链的节点值之和，去更新答案的最大值。 直径可能在下面的某个节点拐弯，不一定经过树根 root。 dfs 返回的是链的长度，不是直径的长度。如果返回直径，那么上面与其他的链继续拼接，得到的就不是直径了。 dfs 返回的是当前子树的最大链长（也可以理解为子树的高度），不包含当前节点和其父节点的这条边。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...

LeetCode 64 https://leetcode.cn/problems/minimum-path-sum/description/ 难度：中等 网格图 DP 题目。f 数组初始化为 INF，f[0][1] = 0。 f[i + 1][j + 1] = min(f[i + 1][j], f[i][j + 1]) + grid[i][j]; 时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。 空间复杂度：O(mn)。 ...

LeetCode 322 https://leetcode.cn/problems/coin-change/description/ 难度：中等 完全背包题目。与 0-1 背包的不同是转移方程中右边的 i 变成 i + 1，说明可以重复取同一个元素。 f[i + 1][c] = min(f[i][c], f[i + 1][c - w[i]] + v[i]) 时间复杂度：O(n⋅amount)，其中 n 为 coins 的长度。 空间复杂度：O(n⋅amount)。 ...

LeetCode 70 https://leetcode.cn/problems/climbing-stairs/description/ 难度：简单 斐波那契数列。f[i] = f[i - 1] + f[i - 2]。 时间复杂度：O(n)。 空间复杂度：O(n)。 ...

LeetCode 32 https://leetcode.cn/problems/longest-valid-parentheses/description/ 难度：困难 本题是一道一维 DP 的题目。f[i] 表示以 i 结尾的最长有效括号的长度。由于有效括号只会以 ‘)’ 结尾，所以只在当前字符为 ‘)’ 时的状态转移。 当前一个字符为 ‘(’ 时，转移到 f[i] = f[i - 2] + 2。 当第 i - f[i - 1] - 1 个字符为 ‘(’ 时，将原本不连续的两段长度合并，即转移到 f[i] = f[i - 1] + f[i - f[i - 1] - 2] + 2。 时间复杂度： O(n)，其中 n 为字符串的长度。我们只需遍历整个字符串一次，即可将 dp 数组求出来。 空间复杂度： O(n)。我们需要一个大小为 n 的 dp 数组。 ...