【算法】常见dp、多状态dp、背包问题、子序列问题

⭐️个人主页：@小羊 ⭐️所属专栏：Linux 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

---

动态规划总结

动态规划通过将问题分解为子问题并存储子问题的解（由记忆化搜索延伸）来避免重复计算。动态规划的关键就是状态和转移。

• 特点：
  1. 重叠子问题：问题可以分解为多个重复的子问题，通过存储子问题的解避免重复计算；
  2. 最优子结构：问题的最优解可以通过子问题的最优解推导出来；
  3. 状态转移方程：通过方程描述问题状态之间的关系，定义如何从子问题的解推导出当前问题的解；
  4. 存储中间结果：通常使用数组或表格存储子问题的解，以便后续使用。

---

• 适用题型：
  1. 最优化问题：如最短路径、最长公共子序列等；
  2. 计数问题：如计算路径数量、组合数等；
  3. 组合问题：如背包问题、硬币找零等；
  4. 序列问题：如最长递增子序列、编辑距离等；

---

• 解题步骤：
  1. 定义状态：明确问题的状态表示；
  2. 确定状态转移方程：找出状态之间的关系；
  3. 初始化：设置初始状态的值；
  4. 计算顺序：确定计算状态的顺序，通常自底向上或自顶向下；
  5. 返回结果：根据存储的状态得到最终解。

---

动态规划的特点：
有后效性，当前的决策会影响到后面的决策。
具有最优子结构的特征。

解这类题的步骤：

1. 定义数组（数学归纳法中的定义函数）：如f[i]表示的是什么，时刻记住你定义的数组的含义。有时题上为了降低难度会帮我们定义。但是有时也会误导我们。方案dp。

2. 写状态转移方程。
   有两种写法：f[i]由什么转移过来。f[i]可以发展到f[i+1]的什么情况。
   通常我们写第一种写法，因为方便表达和下标的书写，理解起来更容易。

3. 初始化。
   初始化f[0]，初始化的方法有两种：根据定义的函数来写，根据实际意思。

4. 枚举遍历所有的情况。用子结构递推到最终的结果。

以上是博主@一只蓝色小鲨鱼的总结，原文链接：动态规划——方案dp（考研复试上机知识点）。

---

1、常见dp

Fibonacci数列

Fibonacci数列

动态规划做法：

#include <bits/stdc++.h>
using namespace std;int main()
{int n;cin >> n;vector<int> dp(sqrt(n));dp[0] = 0, dp[1] = 1;int s1 = 0, s2 = 0;for (int i = 2; i < n; i++){dp[i] = dp[i - 1] + dp[i - 2];if (dp[i] > n){while (dp[i] != n){s1++;dp[i]--;}while (dp[i - 1] != n){s2++;dp[i - 1]++;}break;}}cout << min(s1, s2) << endl;return 0;
}

滚动数组做法：

#include <bits/stdc++.h>
using namespace std;int main()
{int n;cin >> n;int a = 0, b = 1, c = 1;while (true){if (c >= n) break;a = b;b = c;c = a + b; // 这几个顺序不能乱，c = a + b最后算}  cout << min((c - n), (n - b)) << endl;return 0;
}

---

杨辉三角

杨辉三角

#include <bits/stdc++.h>
using namespace std;int main()
{int n;cin >> n;vector<vector<int>> v(n, vector<int>(n, 1));for (int y = 0; y < n; y++){for (int x = 0; x < y + 1; x++){if (y > 1){if (x > 0 && x < y)v[x][y] = v[x][y - 1] + v[x - 1][y - 1];}printf("%5d", v[x][y]);}cout << endl;}return 0;
}

---

三步问题

• 三步问题

class Solution {const int mod = 1e9 + 7;
public:int waysToStep(int n) {if (n < 3) return n;if (n == 3) return 4;vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;dp[3] = 4;for (int i = 4; i <= n; i++)dp[i] = ((dp[i - 1] + dp[i - 2]) % mod + dp[i - 3]) % mod;return dp[n];}
};

---

最小花费爬楼梯

NC296 最小花费爬楼梯

• 注意要爬到楼顶，最后一个数之后才是楼顶，所以dp数组要多开一个空间。

下面的dp[i]表示到第i个台阶所花费的钱。 因此到楼顶就是dp[n]。

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n + 1);dp[0] = dp[1] = 0;for (int i = 2; i <= n; i++)dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);return dp[n];}
};

下面的dp[i]表示从第i个台阶到楼顶所花费的钱。

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n + 1);dp[n - 1] = cost[n - 1];dp[n - 2] = cost[n - 2];for (int i = n - 3; i >= 0; i--)dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);return min(dp[0], dp[1]);}
};

---

孩子们的游戏

• 孩子们的游戏

经典的约瑟夫环问题，也可以利用链表和数组模拟来做。本题通过动态规划可以找到一个规律。

其中 dp[i] 表示 i 个孩子的时候谁拿到了那个礼物。

class Solution {
public:int LastRemaining_Solution(int n, int m) {int f = 0; // 第一个孩子拿到礼物的就死他自己for (int i = 2; i <= n; i++)f = (f + m) % i;return f;}
};

---

解码方法

• 解码方法
  

class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp(n + 1);dp[0] = 1;dp[1] = s[0] != '0';for (int i = 2; i <= n; i++){if (s[i - 1] != '0') dp[i] = dp[i - 1];int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';if (t >= 10 && t <= 26) dp[i] += dp[i - 2];}return dp[n];}
};

---

不同路径

• 不同路径

这题之前用dfs（记忆化搜索）做过，不过还是用动态规划做更简单。这题唯一需要注意的是初始化，不同于一维dp，二维dp考虑的相对较多。

状态：dp[i][j] 表示到达 [i][j] 这个位置有多少种路径。
转移：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

class Solution {int dp[101][101];
public:int uniquePaths(int m, int n) {dp[0][1] = 1;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)dp[i][j] = dp[i - 1][j] + dp[i][j - 1];return dp[m][n];}
};

---

不同路径II

• 不同路径II

和上题一样，就是多了一个障碍物，当遇到障碍物时不用递推就行，也就是不经过这个网格。
还有就是，我们多加了一行一列保证访问不会越界，所以我们的 dp 表和题给矩阵要正确映射。

class Solution {int dp[101][101];
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {dp[0][1] = 1;int m = obstacleGrid.size(), n = obstacleGrid[0].size();for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)if (obstacleGrid[i - 1][j - 1] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];return dp[m][n];}
};

---

珠宝的最高价值

• 珠宝的最高价值

这题我们也是多加了一行一列保证访问不会越界，所以 dp[i][j] 对应的应该是 frame[i - 1][j - 1]。

状态：dp[i][j] 表示到达 [i][j] 这个位置时拿到的所有珠宝的最大价值。
转移：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];。

class Solution {int dp[201][201];
public:int jewelleryValue(vector<vector<int>>& frame) {int m = frame.size(), n = frame[0].size();for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];return dp[m][n];}
};

---

下降路径最小和

• 下降路径最小和

动态规划中初始化步骤不止为了保证不会越界，还为了保证结果的正确性。

二维 dp 表的初始化：

状态：dp[i][j] 表示到达 [i][j] 这个位置时下降路径最小和。
转移：dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1])) + matrix[i-1][j-1]。

最后需要返回到达最后一行的所有路径最小和中的最小值。

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();vector<vector<int>> dp(n+1, vector<int>(n+2, INT_MAX));for (int i = 0; i <= n + 1; i++) dp[0][i] = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1])) + matrix[i-1][j-1];int ret = INT_MAX;for (int i = 1; i <= n; i++)ret = min(ret, dp[n][i]);return ret;}
};

---

最小路径和

• 最小路径和

这道题和“珠宝的最高价值”类似，但是本题是求最小值，所以初始化的时候要特别注意。

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));dp[0][1] = dp[1][0] = 0;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];return dp[m][n];}
};

---

地下城游戏（*）

• 地下城游戏

这道题和以往不同，不能以某个位置为结尾进行状态表示，只能以某个位置为起点表示状态。

状态：dp[i][j] 表示从 [i][j] 这个位置到终点健康点数的最小值。

从起点到终点的过程中，最小健康点数要么不变，要么减小，所以上一个位置的最小健康点数一定大于等于当前位置的最小健康点数，即 dp[i][j] + dungeon[i][j] >= dp[i + 1][j]，且要保证 dp[i][j] 不能小于1。

转移：dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]。

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size(), n = dungeon[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));dp[m][n - 1] = dp[m - 1][n] = 1;for (int i = m - 1; i >= 0; i--)for (int j = n - 1; j >= 0; j--){dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];dp[i][j] = max(1, dp[i][j]); }return dp[0][0];}
};

---

2、多状态dp

面试题 17.16. 按摩师

• 面试题 17.16. 按摩师

class Solution {
public:int massage(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;vector<int> f(n), g(n);f[0] = nums[0];for (int i = 1; i < n; i++){f[i] = g[i - 1] + nums[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[n - 1], g[n - 1]);}
};

---

打家劫舍

• 打家劫舍

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();vector<int> f(n), g(n);f[0] = nums[0];for (int i = 1; i < n; i++){f[i] = g[i - 1] + nums[i];g[i] = max(g[i - 1], f[i - 1]);}return max(f[n - 1], g[n - 1]);}
};

---

打家劫舍 II

• 打家劫舍 II

由于房屋是首尾相连的，第一个房间和最后一个房间只能二选一，也就是第一个房间选不选的问题，最后返回两种情况下的最大值。

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();return max(nums[0] + myrob(nums, 2, n - 2), myrob(nums, 1, n - 1));}int myrob(vector<int>& nums, int l, int r){if (r - l < 0) return 0;int n = nums.size();vector<int> f(n), g(n);f[l] = nums[l];for (int i = l + 1; i <= r; i++){f[i] = g[i - 1] + nums[i];g[i] = max(g[i - 1], f[i - 1]);}return max(f[r], g[r]);}
};

---

删除并获得点数

• 删除并获得点数

对所有数据排序，然后根据下标做一次打家劫舍就OK。

class Solution {
public:int deleteAndEarn(vector<int>& nums) {int m = nums[0];for (int e : nums)m = max(e, m);vector<int> v(m + 1), f(m + 1), g(m + 1);for (int e : nums) v[e]++;for (int i = 1; i <= m; i++){f[i] = v[i] * i + g[i - 1];g[i] = max(f[i - 1], g[i - 1]);}return max(f[m], g[m]);}
};

---

粉刷房子

• 粉刷房子

第 i 个房子的颜色可以有三种状态：红色、蓝色、绿色。
则可以用 dp[i][0]、dp[i][1]、dp[i][2] 分别表示粉刷到第 i 个房子的时候粉刷为红色、蓝色或绿色的最小花费。

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();vector<vector<int>> dp(n + 1, vector<int>(3));for (int i = 1; i <= n; i++)for (int j = 0; j < 3; j++){dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];}return min(dp[n][0], min(dp[n][1], dp[n][2]));}
};

---

买卖股票的最佳时机含冷冻期

• 买卖股票的最佳时机含冷冻期

分析题意，对第i天来说可以有买入、卖出和冷冻期三种状态。分别用 dp[i][0]、dp[i][1]、dp[i][2] 表示。

• 买入：可由买入（昨天买了，今天不买也不卖）和卖出（昨天卖了，今天买）两种状态转移而来；
• 卖出：可由卖出（昨天没买，今天也不买）和冷冻期转移而来；
• 冷冻期：只能有买入（只有手里有股票卖出了才能进入冷冻期，不是由卖出直接转移而来的，注意卖出只是一个状态，不是动作）转移而来。

最大利润一定是最后一天处于卖出状态，或者处于冷冻期。

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(3));dp[0][0] = -prices[0];for (int i = 1; i < n; i++){dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);dp[i][2] = dp[i - 1][0] + prices[i];}return max(dp[n - 1][1], dp[n - 1][2]);}
}; 

---

买卖股票的最佳时机含手续费

• 买卖股票的最佳时机含手续费

这道题只有两种状态：买入和卖出。
用 f[i] 表示第i天的状态为买入，g[i] 表示第i天的状态为卖出。
最大利润一定是最后一天卖出了，也就是 g[n - 1]。

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();vector<int> f(n), g(n);f[0] = -prices[0] - fee;for (int i = 1; i < n; i++){f[i] = max(f[i - 1], g[i - 1] - prices[i] - fee);g[i] = max(g[i - 1], f[i - 1] + prices[i]);}return g[n - 1];}
};

---

买卖股票的最佳时机 III

• 买卖股票的最佳时机 III

还是有两种状态买入和卖出，但本题最多只能完成两笔交易，则可以用 f[i][j] 表示第i天完成j笔交易，并且处于买入状态时的最大利润，g[i][j] 表示第i天完成j笔交易，并且处于卖出状态时的最大利润。

状态转移方程：

• f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
• g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
• 注意：由买入状态转移为卖出，算是完成了一笔交易，所以 f[i - 1][j - 1] 到 g[i][j] 状态转移时交易次数应该+1。

对于第0天来说，不可能完成1笔或2笔交易，因此它们的值是无意义的。初始化防止越界，并且要保证填表的正确，因为要取最大值，所以初始化为最够小的数。

最大利润一定是最后一天处于卖出状态，并且可能交易了0次，1次，2次都有可能。

class Solution {
public:int maxProfit(vector<int>& prices) {const int N = 0x3f3f3f3f;int n = prices.size();vector<vector<int>> f(n, vector<int>(3, -N));auto g = f;f[0][0] = -prices[0];g[0][0] = 0;for (int i = 1; i < n; i++){for (int j = 0; j < 3; j++){f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if (j > 0)g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}int ret = 0;for (int i = 0; i < 3; i++)ret = max(ret, g[n - 1][i]);return ret;}
};

---

买卖股票的最佳时机 IV

• 买卖股票的最佳时机 IV

k的值可能大于prices.size()，可以取一个较小值k = min(k, n / 2)。

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();k = min(k, n / 2);const int N = 0x3f3f3f3f;vector<vector<int>> f(n, vector<int>(k + 1, -N));auto g = f;f[0][0] = -prices[0];g[0][0] = 0;for (int i = 1; i < n; i++){for (int j = 0; j <= k; j++){f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if (j > 0) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}int ret = 0;for (int i = 0; i <= k; i++)ret = max(ret, g[n - 1][i]);return ret;}
};

---

3、子数组、子串

最大子数组和

• 最大子数组和

状态：定义 dp[i] 为以i位置为结尾的所有连续子数组的最大和；
转移：dp[i] = max(0, dp[i - 1]) + nums[i]；

class Solution {
public:int maxSubArray(vector<int>& nums) {int ret = INT_MIN, prev = 0;for (int e : nums){prev = max(0, prev) + e;ret = max(ret, prev);}return ret;}
};

---

环形子数组的最大和

• 环形子数组的最大和

数组是成环的，要我们求所有非空子数组的最大可能和，此时就有两种情况，一是目标子数组是连续的，二是首尾相连的。既然数组成环，那我们可以求它的对立情况，也就是求所有非空子数组的最小可能和，然后由数组总和减去最小可能和，就得到了首位相连的目标情况。

注意：有可能数组中的元素全为负数，此时子数组的最大和只有一个负数元素，但是数组总和减去子数组的最小和就为0了，所以这种情况要特判一下。

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int prev_max = 0, ret_max = INT_MIN;int prev_min = 0, ret_min = INT_MAX, sum = 0;for (int e : nums){prev_max = max(0, prev_max) + e;ret_max = max(ret_max, prev_max);prev_min = min(0, prev_min) + e;ret_min = min(ret_min, prev_min);sum += e;}return sum == ret_min ? ret_max : max(ret_max, sum - ret_min);}
};

---

乘积最大子数组

• 乘积最大子数组

用 f[i] 表示以i位置为结尾的所有子数组的最大乘积，用 g[i] 表示以i位置为结尾的所有子数组的最小乘积。
当 nums[i] < 0 时，需要乘以最小的乘积和，当 nums[i] > 0 时，需要乘以最大的乘积和。

class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();vector<int> f(n + 1, 1);auto g = f;int ret = INT_MIN;for (int i = 1; i <= n; i++){int x = nums[i - 1], y = f[i - 1]*nums[i - 1], z = g[i - 1]*nums[i - 1];f[i] = max(x, max(y, z));g[i] = min(x, min(y, z));ret = max(ret, f[i]);}return ret;}
};

---

---

---

4、组合方案

李白打酒加强版（lqb）

• 一般求合法的个数、顺序、排列、方案等且范围不是很大，大概率是用动态规划做。

本题的关键所在是：最后一次遇到花，且酒恰好喝完。

动态规划的两大要素：状态和转移。
状态：题中共有三个状态：店、花、酒。所以设 dp[i][j][k] 表示经过i家店，j朵花，壶里还有k斗酒的方案数。
转移：假设李白的壶中此时有k斗酒，则此时的状态 dp[i][j][k] 可以由 dp[i-1][j][k/2] （上一次遇到的是店，但是需要注意此时的k必须是偶数，因为此时的k是由上一次遇到店翻倍而来）和 dp[i][j-1][k+1] （上一次遇到的是花）转移而来。

最后返回 dp[n][m-1][1]，因为要保证最后一次遇到的是花，且酒恰好还剩一斗。

#include <bits/stdc++.h>
using namespace std;const int mod = 1e9 + 7;
// dp[i][j][k]表示经过i家店，j朵花，壶里还有k斗酒的方案总数 
int dp[110][110][110];int main()
{int n, m;cin >> n >> m;dp[0][0][2] = 1;for (int i = 0; i <= n; i++){for (int j = 0; j <= m; j++){for (int k = 0; k < m; k++){if (k % 2 == 0 && i > 0){dp[i][j][k] += (dp[i - 1][j][k / 2]) % mod; }if (j > 0){dp[i][j][k] += (dp[i][j - 1][k + 1]) % mod;}}}}cout << dp[n][m - 1][1] << endl;return 0;}

---

---

3、背包问题

4、最长公共子序列

5、最长递增子序列

• 最长递增子序列

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size(), ret = 0;;vector<int> dp(n, 1);for (int i = n - 1; i >= 0; i--){for (int j = i + 1; j < n; j++){if (nums[j] > nums[i])dp[i] = max(dp[i], dp[j] + 1);}ret = max(ret, dp[i]);}return ret;}
};

---

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~