| 0070-爬楼梯 |
\(dp_{n} = dp_{n - 1} + dp_{n - 2} \quad dp_1 = 1,dp_2 = 2\) |
| 0746-使用最小花费爬楼梯 |
\(dp_n = min(dp_{n - 1} + cost[n - 1], dp_{n - 2} + cost[n - 2]) \quad dp_0 = 0,dp_1 = 0\) |
| 0198-打家劫舍 |
\(dp_n = max(dp_{n-2} + nums[n], dp_{n-1}) \quad dp_{n2} = 0, dp_{n1} = 0\) |
| 0213-打家劫舍 II |
分为三种情况，不偷第一家，不偷最后一家，第一家最后一家都不偷,显然第三种情况小于前两种情况，因此计算前两种情况最大值。 |
| 0091-解码方法 |
\(dp_n = dp_{n-1} ? \{s[n] \neq 0\} \quad + dp_{n-2} ? \{s[n-1]\neq 0 \& s[n-1] * 10 + s[n] <= 26\} \quad dp_{n1} = 1, dp_0 = s[0]\neq 0 ? 1 : 0\) |
| 1043-分隔数组以得到最大和 |
dp为以n结尾分割的最大和,\(dp_i = max(dp_j + maxv\times(i - j))\) |
| 0139-单词拆分 |
\(dp_n\)表示字符串前n个字符组成的字符串是否能被空格拆分成若干个字典中出现的单词。\(dp_i = dp_j \& check(s[j..i-1])\) |
| 1869-哪种连续子字符串更长 |
dp[2]表示第n个结尾字符串为‘0’‘1’的最长长度。\(dp_n[0/1] = dp_{n - 1}[0/1] + 1 ? {s[n] = s[n-1]} : 0\) |
| 0221-最大正方形 |
我们用 dp(i,j)表示以 (i,j)为右下角，且只包含1的正方形的边长最大值。\(dp(i,j) = matrix[i,j] == 0 ? 0 : min(dp[i - 1, j], dp[i-1, j-1], dp[i, j-1]) + 1 \quad dp(0,0) = matrix[0, 0] == 0 ? 0 : 1\) |
| 1277-统计全为 1 的正方形子矩阵 |
dp(i,j)也表示以 (i, j) 为右下角的正方形的数目为（即边长为 1, 2, ..., x 的正方形各一个） |
| 256-粉刷房子 LCR 091. 粉刷房子 |
用 dp(i,j)表示粉刷到第i号房子且第i号房子被粉刷成第j种颜色时的最小花费成本。\(dp(i, 0) = min(dp(i-1,1),dp(i-1, 2) + costs[i][0]) \\ dp(i, 1) = min(dp(i-1,0),dp(i-1, 2) + costs[i][1]) \\ dp(i, 2) = min(dp(i-1,0),dp(i-1, 1) + costs[i][2])\) |
| 0590-斐波那契数 |
\(dp_n = dp_{n-1} + dp_[n-2] \quad dp_0 = 0, dp_1 = 1\)矩阵快速幂(O(logn))：\(\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} F_n + F_{n-1} \\ F_n \end{bmatrix} = \begin{bmatrix} F_{n+1} \\F_n \end{bmatrix} 得到 \begin{bmatrix} F_{n+1} \\F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n * \begin{bmatrix} F_{1} \\F_0 \end{bmatrix}\) |
| 53-最大子数组和 |
dp(n)代表以第n个数结尾的连续子数组的最大和, 考虑 nums[n]单独成为一段还是加入 dp(n−1) 对应的那一段。\(dp_n = max(dp_{n-1} = nums[n], nums[n])\) |
| 300-最长递增子序列 |
定义 dp[i] 为考虑前i个元素，以第i个数字结尾的最长上升子序列的长度。\(dp_i = max(dp_{[0...i]}) + 1\) |
| 673-最长递增子序列的个数 |
cnt[i] 表示以 nums[i]结尾的最长上升子序列的个数。对于 cnt[i]，其等于所有满足 dp[j]+1=dp[i] 的 cnt[j]之和。 |
| 1027-最长等差数列 |
|
| 873-最长的斐波那契子序列的长度 |
|
| 516-最长回文子序列 |
将字符串翻转，然后求两个字符串的最长公共子序列 |
| 1143-最长公共子序列 |
dp[i][j] 表示 text1[0:i]和 text2[0:j]的最长公共子序列的长度。\(if \ text_1[i-1] == text_2[j-1] \ dp[i][j] = dp[i-1][j-1] + 1 \ else \ dp[i][j] = max(dp[i-1][j], dp[i][j-1]) \quad dp[0][j] = dp[i][0] = 0\) |
| 72-编辑距离 |
1.在单词 A 中插入一个字符；2.在单词 B 中插入一个字符；3.修改单词 A 的一个字符。 |
| 62-不同路径 |
dp[i][j] 是到达 i, j 最多路径。\(dp[i][j] = dp[i-1][j] + dp[i][j-1] \quad dp[0][j]=1, dp[i][0] = 1\) |
| 64-最小路径和 |
设 dp 为大小 m×n 矩阵，其中 dp[i][j]的值代表直到走到 (i,j)的最小路径和。\(dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] \quad dp[0][0] = grid[0][0]\) |
| 121-买卖股票的最佳时机 |
dp[i][j]下标为 i 这一天结束的时候，手上持股状态为 j (0不持股，1持股)时，我们持有的现金数。1.今天不持股-a.昨天不持股, b.昨天持股，今天卖出，2. 今天持股-a.昨天持股不做，b.昨天不持股，买入。\(dp[i][0] = max(dp[i-1][0], dp[i-1][1]+price[i]) dp[i][1] = max(dp[i-1][1], -price[i])\) |
| 122-买卖股票的最佳时机 II |
|
| 123-买卖股票的最佳时机 III |
|
| 188-买卖股票的最佳时机 IV |
|
| 309-买卖股票的最佳时机含冷冻期 |
|
| 714-买卖股票的最佳时机含手续费 |
|
| 416-分割等和子集 |
|
| 01背包 |
dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。不放和放物体取最大值\(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])\) |