蓝桥杯刷题_day7_动态规划

文章目录

DAY7
- 下降路径最小和
- 最小路径和
- 地下城游戏

DAY7

下降路径最小和

【题目描述】
给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

【输入样例】

matrix = [[2,1,3],[6,5,4],[7,8,9]]

【输出样例】

【数据规模与约定】

n == matrix.length == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100

【解题思路】

【C++程序代码】

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

最小路径和

【题目描述】
给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

【输入样例】

grid = [[1,3,1],[1,5,1],[4,2,1]]

【输出样例】

【数据规模与约定】

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

【解题思路】
通过题目得出dp[i]表示的是走到当前位置时的最小路径和。由因为题目要求只能向下或者向右走一步，所以dp[i]应该是上面的格子或者右边的格子其中小的那个加上当前位置的值。

【C++程序代码】

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

地下城游戏

【题目描述】
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为_负整数_，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为_正整数_，则表示骑士将增加健康点数）。

为了尽快解救公主，骑士决定每次只向右或向下移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意： 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

【输入样例】

dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]

【输出样例】

【数据规模与约定】

m == dungeon.length
n == dungeon[i].length
1 <= m, n <= 200
-1000 <= dungeon[i][j] <= 1000

【解题思路】
这个问题是一个典型的动态规划问题。我们需要找到英勇骑士拯救公主时所需的最低初始健康点数。为了解决这个问题，我们可以从终点开始（即公主所在的右下角），逆向思考骑士到达每个房间所需的最低健康点数。这样，我们可以确保骑士在任何时刻的健康点数都不会低于1。

动态规划状态定义
我们定义 dp[i][j] 为从点 (i, j) 到达终点所需的最低健康点数。因此，dp[0][0] 就是我们要找的答案。
边界条件
1. dp[m-1][n-1]：这是公主所在的房间，骑士至少需要1点健康，如果这个房间的值为正，则骑士只需要1点健康即可；如果为负，则骑士需要足够的健康点数以确保他在离开这个房间时至少有1点健康。因此，dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])。
2. 边界的其他点：对于最下面一行（row）和最右边一列（col），骑士只能向右或者向下移动，因此每个点的 dp 值依赖于它右边或者下面的点的 dp 值。
状态转移方程
对于非边界点 (i, j)，骑士可以从 (i+1, j)（下方）或 (i, j+1)（右方）到达 (i, j)。因此，dp[i][j] 依赖于 dp[i+1][j] 和 dp[i][j+1]。骑士在 (i, j) 点的健康点数必须足以让他能够到达 (i+1, j) 或 (i, j+1)，同时保持至少1点健康。因此，状态转移方程为：
dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
这里 max(1, x) 确保了在任何时刻骑士的健康点数至少为1。
计算顺序
由于我们从终点开始反向计算，所以我们应该从右下角开始，首先计算最后一行和最后一列，然后向左上方移动，直到计算到 dp[0][0]。
实现细节
1. 初始化 dp 数组，除了 dp[row-1][col-1] 之外，其他所有 dp[row][col] 均设为 INT_MAX。
2. 从右下角开始逆向遍历，计算每个 dp[i][j]。
3. 返回 dp[0][0] 作为结果。

【C++程序代码】

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

代码详解

在这段代码中，我们初始化了一个 (row + 1) x (col + 1) 大小的 dp 数组，并将除 dp[row][col - 1] 和 dp[row - 1][col] 外的所有元素设置为 INT_MAX，这样做是为了确保在逆向计算过程中，我们不会用到这些未初始化的状态值。
然后我们从 dp[row - 1][col - 1] （即公主所在的房间）开始向左上方逆向遍历，对每一个格子 (i, j)，计算所需的最小初始健康点数。这个数值是根据它的右边 (i, j+1) 和下边 (i+1, j) 的两个格子的 dp 值来得到的。我们取这两个 dp 值中较小的一个，然后减去当前格子的 dungeon[i][j] 值（如果当前格子是恶魔，dungeon[i][j] 将是负数；如果是魔法球或空房间，dungeon[i][j] 将是非负数），以此来计算骑士在进入格子 (i, j) 前，所需的最小健康点数。最后，我们需要确保这个数值至少为1，因为骑士的健康点数不能少于1。
最终，dp[0][0] 就是我们要找的答案，即骑士从左上角出发所需的最小初始健康点数。