当前位置：首页 > news >正文

【经典DP】三步问题 / 整数拆分 / 不同路径II / 过河卒 / 下降路径最小和 / 地下城游戏

news 来源：原创 2025/9/21 4:19:32

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

动图描述

动态规划总结

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

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

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

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

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

解这类题的步骤：

定义数组（数学归纳法中的定义函数）：如f[i]表示的是什么，时刻记住你定义的数组的含义。有时题上为了降低难度会帮我们定义。但是有时也会误导我们。方案dp。
写状态转移方程。
有两种写法：f[i]由什么转移过来。f[i]可以发展到f[i+1]的什么情况。
通常我们写第一种写法，因为方便表达和下标的书写，理解起来更容易。
初始化。
初始化f[0]，初始化的方法有两种：根据定义的函数来写，根据实际意思。
枚举遍历所有的情况。用子结构递推到最终的结果。

以上是博主@一只蓝色小鲨鱼的总结，原文链接：动态规划——方案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;
}

BC140 杨辉三角

BC140 杨辉三角

在这里插入图片描述

#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;
}

杨辉三角

Leetcode——杨辉三角

在这里插入图片描述

类似一个二维数组，用vector<vector<int>>会很方便。

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv(numRows);for (int i = 0; i < numRows; i++){vv[i].resize(i + 1, 1);}for (int i = 2; i < numRows; i++){for (int j = 1; j < vv[i].size() - 1; j++){vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];}}return vv;}
};

三步问题

三步问题

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];}
};

整数拆分

整数拆分

在这里插入图片描述

class Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1);for (int i = 2; i <= n; i++)for (int j = 1; j <= i / 2; j++)dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));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];}
};

过河卒

过河卒

在这里插入图片描述

#include <asm-generic/errno.h>
#include <bits/stdc++.h>
using namespace std;int main()
{int n, m, x, y;cin >> n >> m >> x >> y;vector<vector<long>> dp(n + 2, vector<long>(m + 2));x += 1, y += 1;dp[0][1] = 1;for (int i = 1; i <= n + 1; i++){for (int j = 1; j <= m + 1; j++){if (i != x && j != y && abs(i - x) + abs(j - y) == 3 || (i == x && j == y)) continue;else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}cout << dp[n + 1][m + 1] << endl;return 0;
}

珠宝的最高价值

珠宝的最高价值

在这里插入图片描述
这题我们也是多加了一行一列保证访问不会越界，所以 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];}
};

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

目录

动态规划总结

Fibonacci数列

BC140 杨辉三角

杨辉三角

三步问题

最小花费爬楼梯

孩子们的游戏

解码方法

整数拆分

不同路径

不同路径II

过河卒

珠宝的最高价值

下降路径最小和

最小路径和

地下城游戏 *

相关文章：