一文带你掌握动态规划（一）

🕗 发布于 2024-10-13 02:15 动态规划算法

1. 什么是动态规划

动态规划（Dynamic Programming，简称DP），是一种解决多阶段决策问题的数学优化方法。它将原问题分解成若干个子问题，通过解决子问题只需解决一次并将结果保存下来，从而避免了重复计算，提高了算法效率。

动态规划的核心思想是利用子问题的解来避免重复计算，并通过记录已解答的结果来提高效率。所以动态规划本质上是使用空间来换时间的一种做法。

2. 动态规划的步骤

dp表是根据题目要求所列的一个表，例如求斐波那契数，我们可以弄一个dp数组，让dp[i]的含义为第i个斐波那契数

状态表示：dp表里面的值所表示的含义
推导状态转移方程：dp[i]等于什么
初始化：初始化dp表中的某些值，保证填表时不会越界。
填表：确定填表顺序，保证填写当前状态的时候，所需要的状态已经计算过了，然后根据状态转移方程进行填表就行了。
返回值：dp表中保存了最终结果，根据题目要求返回结果。

举个例子：求斐波那契数

状态表示：dp[i]表示的是第i个斐波那契数，
状态转移方程：dp[i] = dp[i-1] + dp[i - 2]。
dp[0]和dp[1]要进行初始化，否则使用状态转移方程时会越界。
要填写dp[i]，要保证i-1和i-2都填写好，所以要从左向右填表
题目要求第i个斐波那契数，则返回dp[i]即可。

3. 动态规划的应用

动态规划广泛应用于解决一些优化问题，如最短路径问题、最长公共子序列、背包问题等。以下是一些常见的应用场景：

最短路径问题：比如 Dijkstra 算法和 Floyd-Warshall 算法。
背包问题：包括 0/1 背包问题和背包问题的变种。
最长公共子序列：求解两个序列的最长公共子序列的长度。
字符串编辑距离：计算两个字符串之间的最小编辑操作次数，包括插入、删除和替换。
最大子数组和：求解数组中连续子数组的最大和。

4. 动态规划的例题

动态规划最重要的就是得出状态表示，最难的一步是推导出状态转移方程，理解一个算法的最好方式就是自己能用算法思想解决一道例题。接下来，我将会通过一些经典的例题带大家掌握动态规划。

4.1 简单动态规划

4.1.1 泰波那契数

题目链接：1137. 第 N 个泰波那契数 - 力扣（LeetCode）

这题几乎和斐波那契数一样，状态表示和状态转移方程都很好得到，题目中差不多已经告诉你答案了。

状态表示：dp[i]表示第i个泰波那契数
推导状态转移方程：dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
初始化：初始化dp[0]，dp[1]，dp[2]
填表：从左向右填表
返回值：dp[i]就是最终结果，返回dp[i]。

题解：

class Solution 
{
public:
    int tribonacci(int n) 
    {
        //处理一下边界情况，防止n比较小时出现越界情况
        if (n == 0)
            return 0;
        if (n == 1 || n == 2)
            return 1;

        vector<int> dp(n + 1); //1.创建dp表
        dp[0] = 0;             //2.初始化
        dp[1] = dp[2] = 1;

        //3.填表
        for (size_t i = 3; i <= n; i++)
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        
        return dp[n];
    }
};

4.1.2 三步问题

题目链接：面试题 08.01. 三步问题 - 力扣（LeetCode）

我们先来分析一下，如果只有1个台阶，那只有一种方法：从0到1

如果有两个台阶，那么此时可以从0一次跳2个台阶直接到2，也可以从1一次跳1个台阶到2，所以有2种方法。

如果有三个台阶，可以从从0一步跳三个台阶到3，也可以从1一步跳2个台阶到3，也可以2一步跳一个台阶到3，但是这种方式最终结果不是3种，而是4种，因为0到2其实是有两种方法的，这两种方法到达3都只需要再走一步。

如果有四个台阶，那么可以从1，2，3个台阶再走1步到4。0到1有1种方法，0到2有2种方法，0到3有4种方法，所以0到4一共有1+2+4=7种方法。

综上，我们可以发现一个规律：第 i 个台阶其实是可以从i - 3, i - 2, i - 1个台阶走一步到达，所以从 0 到第 i 个台阶的方法数就 = 从0 到i-3台阶的方法数 + 从0 到i-2台阶的方法数 + 从0 到i-1台阶的方法数。其实和上一道泰波那契数是一样的。

根据上面的，我们可以来填写动态规律的步骤了。

状态表示：dp[i]表示到第i个台阶的方法数
推导状态转移方程：dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
初始化：初始化dp[0]，dp[1]，dp[2]
填表：从左向右填表
返回值：dp[i]就是最终结果，返回dp[i]。

题解：

class Solution 
{
public:
    int waysToStep(int n) 
    {
        //防止n为1/2时，初始化会出现越界，特殊处理一下
        if (n == 1 || n == 2)
            return n;

        //1.创建dp表
        vector<long long> dp(n + 1);
        //2.初始化
        dp[0] = 1;     
        dp[1] = 1;
        dp[2] = 2;

        //3.填表
        for (size_t i = 3; i <= n; i++)
            dp[i] = (dp[i - 3] + dp[i - 2] + dp[i - 1]) % 1000000007;

        //4.返回结果
        return dp[n];
    }
};

4.1.3 使用最小花费爬楼梯

题目链接：LCR 088. 使用最小花费爬楼梯 - 力扣（LeetCode）

在做动态规划题目时，我们通常会根据经验和题目意思来设定状态表示。这里的经验指的是：以i位置为结尾 / 以i位置为开头。

比如这题我们的状态表示可以是：从头到达 i 位置时的最小花费，或者是以 i 位置为起点到达楼顶的最小花费。

接下来，我会通过这两种不同的状态表示来解这道题

dp[i]表示：到达 i 位置时的最小花费

到达 i 位置有两种情况，一是从 i-2 到 i ，一种是从 i-1 到 i。

那么dp[i]就很好得到了

1. dp[i] = 从 i-2 位置，支付cost[i-2] 然后走2步到达i -> dp[i-2] + cost[i-2]
2. dp[i] = 从 i-1 位置，支付cost[i-1] 然后走1步到达i -> dp[i-1] + cost[i-1]

那我们只需要计算出这两个值的最小值就是dp[i]的值，所以我们的状态转移方程就是：dp[i] = min( dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])。

接下来我们就可以填写动态规划的几个步骤了

状态表示：到达 i 位置时的最小花费
推导状态转移方程：dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])
初始化：初始化dp[0]，dp[1]
填表：从左向右填表
返回值：dp[i]就是最终结果，返回dp[i]。

题解：

class Solution 
{
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        //1.创建dp数组
        int n = cost.size();
        vector<int> dp(n + 1);

        //2.初始化
        dp[0] = 0;
        dp[1] = 0;

        //3.填表
        for (size_t i = 2; i <= n; i++)
            dp[i] = min(dp[i-2]+cost[i-2], dp[i-1]+cost[i-1]);

        //4.返回结果
        return dp[n];
    }
};

dp[i]表示：以 i 位置为起点到达楼顶的最小花费。

i 位置有两种情况，一是走一步到达 i+1，然后从 i+1 的位置到终点，二是走两步到达 i+2，然后从 i+2 的位置到终点。

1.dp[i]支付cost[i]，往后走一步，从i+1的位置出发到终点 -> dp[i] = dp[i+1] + cost[i];
1.dp[i]支付cost[i]，往后走两步，从i+2的位置出发到终点 -> dp[i] = dp[i+2] + cost[i];

那么dp[i] = min(dp[i+1] + cost[i], dp[i+2] + cost[i])。

状态表示：以 i 位置为起点到达楼顶的最小花费
推导状态转移方程：dp[i] = min(dp[i+1] + cost[i], dp[i+2] + cost[i])。
初始化：因为计算dp[i]时要有dp[i+1]和dp[i+2]，所以初始化dp[n-1]=cost[n-1]和dp[n-2]=cost[n-2]即可。(最后两个楼梯只要花费本身的钱就能一步到楼顶）
填表：从右向左填表
返回值：min(dp[0]，dp[1])，最开始可以从0位置或者1位置开始。

题解：

class Solution 
{
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        //1.创建dp表
        int n = cost.size();
        vector<int> dp(n);

        //2.初始化
        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];

        //3.填表
        for (size_t i = n - 3; i >= 0; i--)
            dp[i] = cost[i] + min(dp[i+1], dp[i+2]);
    
        //4.返回结果
        return min(dp[0], dp[1]);
    }
};

4.1.4 解码方法

题目链接：91. 解码方法 - 力扣（LeetCode）

我们来根据测试案例来分析一下题意

12可以看成单独的1和2，单独解码成AB，也可以将12看成一个整体解码成L

226，如果看成三个数解码，就变成了BBF，如果将22和6分开解码就变成了VF，如果将2和26分开解码就变成了BZ。

06不存在解码方式，因为单独一个0无法解码，如果将06放在一起也不行，因为不能存在前导0。

算法原理：

状态表示

我们先要想到状态表示是什么，我们可以通过经验+题目要求来猜测状态表示，通过这个状态表示去推导状态转移方程，如果能推导出正确结果，那么我们猜测的状态表示就是正确的。

这里的经验就是：dp[i]表示的是以某个位置为结尾.... / dp[i]表示的是以某个位置为起点....。

那么这题我们可以大胆假设，dp[i]表示的是以i位置为结尾的编码总数。

状态转移方程

推导状态转移方程时，我们需要根据最近的一步，进一步划分。那么到达i时，根据题意，我们可以让s[i]单独解码，也可以让s[i]和s[i-1]一起解码。

1.s[i]单独解码，如果s[i]的值不为0的情况下，解码成功；如果s[i]等于0，那么解码失败。如果s[i]能单独解码，其实相当于是前面i-1个字符所有的解码情况加上第i个字符，也就是说dp[i] = dp[i - 1]，如果s[i]解码失败，则整个字符串都无法解码，dp[i] = 0。
2.s[i]和s[i-1]一起解码，s[i-1] * 10 + s[i]一定要在[10, 26]之间，如果结果处于这个范围之内，视为解码成功，解码成功相当于是前面i-2个字符的所有解码情况加上 i-1和i两个字符的解码结果，也就是说dp[i] = dp[i-2]，解码失败则整个字符串都无法解码，dp[i] = 0。

总结一下：

dp[i] = dp[i-1] + dp[i-2] （都解码成功的情况）
dp[i] = dp[i-1] (dp[i]和dp[i-1]无法一起解码）
dp[i] = dp[i-2] (dp[i]无法解码）
dp[i] = 0 (两种情况都不符合）

为什么说s[i]能单独解码，其实相当于是前面i-1个字符所有的解码情况加上第i个字符。

前面i-1个字符可能会有很多种情况，假如说前面i-1个字符的解码方式为: aba，acd，efe等，如果第i个字符假设解码为g，那么也只是在前面的解码方式后多加一个g，变成：abag，acdg，efeg，但是解码方式数是不变的，所以dp[i] = dp[i-1]。

总结

1.状态表示：以i位置为结尾的编码总数
2.推导状态转移方程：
- dp[i] = dp[i-1] + dp[i-2] （都解码成功的情况）
- dp[i] = dp[i-1] (dp[i]和dp[i-1]无法一起解码）
- dp[i] = dp[i-2] (dp[i]无法解码）
- dp[i] = 0 (两种情况都不符合）
3.初始化：初始化dp[0]和dp[1]，如果这两个值出现等于0，说明不存在解码方法。
4.填表：从左向右填表
5.返回值：dp[n-1]就是最终结果，返回dp[n-1]。
题解：

class Solution 
{
public:
    int numDecodings(string s) 
    {
        int n = s.size();
        //防止n为1时，后面的dp[1]出现越界访问
        if (n == 1)
            return s[0] != '0';

        //创建dp表
        vector<int> dp(n);

        //初始化
        dp[0] = s[0] != '0'; //能解码为1，不能解码为0
        dp[1] = s[1] != '0'; //先判断能否单独解码
        int ret = (s[0] - '0') * 10 + s[1] - '0';
        dp[1] += (10 <= ret && ret <= 26); //再判断能否和前面的一起解码

        if (dp[0] == 0 || dp[1] == 0)
            return 0;
        
        for (size_t i = 2; i < n; i++)
        {
            //判断能否单独解码
            if ('1' <= s[i] && s[i] <= '9')
                dp[i] += dp[i-1];
            
            //判断能否和i-1一起解码
            ret = (s[i-1] - '0') * 10 + s[i] - '0';
            if (10 <= ret && ret <= 26)
                dp[i] += dp[i-2];
        }

        return dp[n-1];
    }
};

4.2 路径问题

4.2.1 不同路径

题目链接：LCR 098. 不同路径 - 力扣（LeetCode）

算法原理：

状态表示

前面说到过，根据经验，我们可以让dp[i]表示为以i位置为结尾.... / 以i位置为起点...。

那么我们这题可以让dp[i][j]表示为到达[i][j]位置时的总路径数。

状态转移方程

求解状态转移方程时要根据最近的一步来划分问题，也就是说如何到达[i][j]，根据题目意思来看有两种方法，要么是从左边到达[i][j]也就是从[i][j-1]，要么是从上面到达[i][j]也就是[i-1][j]。

如果是从左边[i][j-1]到达[i][j]，从起点到达[i][j-1]有x种方法，这x种方法再走一步都能到达[i][j]，所以dp[i][j] += 起点到[i][j-1]的总方法数；同理，从上面走也是一样的。所以dp[i][j] = 起点到[i][j-1]的总方法数 + 起点到[i-1][j]的总方法数，即dp[i][j] = dp[i-1][j] + dp[i][j-1]。

初始化

因为我们需要找到dp[i][j]上面和左边的值，为了防止发生越界访问和便于代码的编写，我们可以额外添加一行和一列。真正的dp表是从[1][1]开始的。

现在我们需要初始化第一行和第一列为0，而将[0][1]或者[1][0]的位置初始化为1。因为如果填[i][j]位置时，dp[i][j] = dp[i][j-1] + dp[i-1][j]，如果这两个位置都为0的话，就不对了，因为起点到[1][1]至少有一种方法。

总结

1.状态表示：到达[i][j]位置时的总路径数
2.推导状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
3.初始化：需要额外添加一行和一列，并初始化第一行和第一列为0，还要将[0][1]或者[1][0]的位置初始化为1
4.填表：从左向右，从上向下填表
5.返回值：dp[m][n]就是最终结果，返回dp[m][n]。

题解：

class Solution 
{
public:
    int uniquePaths(int m, int n) 
    {
        //创建dp表
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        //初始化
        dp[0][1] = 1;

        //填表
        for (size_t i = 1; i < m + 1; i++)
            for (size_t j = 1; j < n + 1; j++)
                dp[i][j] = dp[i-1][j] + dp[i][j-1];

        //返回结果
        return dp[m][n];
    }
};

4.2.2 珠宝的最高价值

题目链接：LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

简单来说，就是从左上角到右下角，价值最高的路径。

算法原理：

状态表示

和前面一样，我们可以根据经验来“猜测”状态表示，根据题意，我们可以让dp[i][j]表示为到达[i][j]位置时的最大价值。

状态转移方程

通过状态表示，我们可以来推到一下状态转移方程。到达[i][j]时有两种情况，第一种是从[i][j]的左边[i][j-1]到达[i][j]，第二种是从[i][j]的上面[i-1][j]到达[i][j]。

1. 从[i][j]的左边到达[i][j]：dp[i][j]的值为dp[i][j-1] + frame[i][j]（当前位置的值）
2. 从[i][j]的上面到达[i][j]：dp[i][j]的值为dp[i-1][j] + frame[i][j]

我们需要选择两个计算结果中较大的那个。

dp[i][j] = frame[i][j] + max(dp[i][j-1], dp[i-1][j])。

初始化

因为我们需要找到dp[i][j]上面和左边的值，为了防止发生越界访问和便于代码的编写，我们可以额外添加一行和一列。真正的dp表是从[1][1]开始的。

现在我们需要初始化第一行和第一列，因为这道题的数据都是大于等于0的，所以我们将第一行和第一列设置为0即可。

总结

1.状态表示：到达[i][j]位置时的最大价值
2.推导状态转移方程：dp[i][j] = frame[i][j] + max(dp[i][j-1], dp[i-1][j])
3.初始化：需要额外添加一行和一列，并初始化第一行和第一列为0。
4.填表：从左向右，从上向下填表
5.返回值：dp[m][n]就是最终结果，返回dp[m][n]。

题解：

class Solution 
{
public:
    int jewelleryValue(vector<vector<int>>& frame) 
    {
        int n = frame.size();
        int m = frame[0].size();

        //1.创建dp表
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        //2.填表
        for (size_t i = 1; i < n + 1; i++)
            for (size_t j = 1; j < m + 1; j++)
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + frame[i-1][j-1];

        //3.返回结果
        return dp[n][m];
    }
};

4.2.3 下降路径最小和

题目链接：931. 下降路径最小和 - 力扣（LeetCode）

第一点可以下降到他的下一层的相邻的三个位置，可以从第一行任意位置开始，找到下降的路径和最短的那个。

算法原理：

状态表示

结合经验 + 题目要求，我们可以假设dp[i][j]表示到达[i][j]位置时的最小下降路径和。（这道题和前面两题是一样的，根据题目要求什么，我们就假设dp表示的是什么，如果假设推导不出状态转移方程再更改状态表示）

状态转移方程

状态转移方程需要我们根据最近的一步来划分。最近的一步就是如何到达的dp[i][j]。有三种情况：1.从左上方[i-1][j-1]到达[i][j]，到头到达左上方时的最短下降路径和 + matrix[i][j]（[i][j]位置的值）就是从[i-1][j-1]到达[i][j]的最短下降路径和，即dp[i][j] = dp[i-1][j-1] + matrix[i][j]。
2.从正上方[i-1][j]到达[i][j]，同理，dp[i][j] = dp[i-1][j] + matrix[i][j]。
3.从右上方[i-1][j+1]到达[i][j]，同理，dp[i][j] = dp[i-1][j+1] + matrix[j][j]。

所以我们只需要找到这三条路径中最小的那个就是到达[i][j]时的最小下降路径，dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1]));

初始化

因为我们需要找到dp[i][j]左上方，正上方，右上方，为了防止发生越界访问和便于代码的编写，我们可以额外添加一行和两列，有色部分是真正的dp表，而白色部分是额外添加的行列。

现在我们需要初始化第一行为0，因为第一行设置为0后，在正式填写dp表的第一行(有色部分)时不会影响结果。因为dp[i][j]是上面相邻三个位置中的最小值加上本身的值，只有上一行为0才能让dp表的第一行的值为本身。

那么旁边的两列应该设置成什么，如果设置为0，其实是不行的，因为在计算两侧的dp值时，旁边的两列的值应该是不可取的（范围之外）。如果旁边的值为0，那么可能会影响到最终结果。为了让旁边的两列值不影响结果，应该设置为 +∞

总结

1.状态表示：到达[i][j]位置时的最小下降路径和
2.推导状态转移方程：dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])
3.初始化：额外添加一行两列，第一列和最后一列设置为+∞，第一行设置为0。
4.填表：从左向右，从上向下填表
5.返回值：遍历dp表最底层，找到最小的那个返回结果。

题解：

class Solution 
{
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        int n = matrix.size();
        int m = matrix[0].size();

        //创建dp表+初始化
        vector<vector<int>> dp(n + 1, vector<int>(m + 2, INT_MAX));
        for (size_t i = 0; i < m + 2; i++)
            dp[0][i] = 0;

        //填表
        for (size_t i = 1; i < n + 1; i++)
            for (size_t j = 1; j < m + 1; 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 (size_t i = 1; i < m + 1; i++)
            if (dp[n][i] < ret)
                ret = dp[n][i];
        return ret;
    }
};

4.2.4 地下城游戏

题目链接：174. 地下城游戏 - 力扣（LeetCode）

算法原理：

状态表示

这道题我们使用经验 + 题目要求的方式来定义状态表示，经验指的是以i位置为结尾... / 以i位置为起点.... ，在前面几题中，我们使用的是以i位置为结尾。

那么这道题我们先试一下能否使用以i位置为结尾的方式。dp[i][j]表示从起点到达[i][j]位置时的最小健康点数，但是这种状态表示是无法推出状态转移方程的。原因就在于，无法根据最近的一步来划分，如果想要得到dp[i][j]，不但需要得到[i][j]位置前面的dp值，而且还需要得到[i][j]位置后面的值才能更新出正确的dp[i][j]（有后效性），这显然推导不出来。

在动态规划中，无后效性是一个基本的前提条件。无后效性指的是在某个阶段的状态一旦确定，那么在这个阶段之后的过程中，决策的选择就不会受到之前阶段状态和决策的影响。换句话说，一个阶段的决策只依赖于当前状态，而与之前的历史状态无关。这个特性使得我们可以将问题分解成阶段来解决，每个阶段的解决方案都是独立的。

既然这种方式不行，那么我们可以试一下以i位置为起点的方式定义状态表示。dp[i][j]表示：从[i][j]位置到达终点所需的最少健康点数。

状态转移方程

以[i][j]位置为起点到达终点，那么[i][j]位置有两种情况，1.向下走 2.向右走。如果[i][j]位置想要走到下面或者右边必须要满足dp[i][j] + dungeon[i][j] >= dp[i+1][j] / dp[i][j+1]。因为想要到下一个位置，那至少要先保证到下一个位置时的健康点数不能 <= 0。

1. 向右走 dp[i][j] >= dp[i][j+1] - dungeo[i][j]
2. 向下走 dp[i][j] >= dp[i+1][j] - dungeo[i][j]

我们要求的是最低健康点数，所以dp[i][j] = min(dp[i][j+1], dp[i+1][j]) - dungeo[i][j]。但是这个值可能是一个负数，但是这不符合逻辑，因为dp[i][j]表示的是从[i][j]位置开始所需的最少健康点数，这个值最少为1。所以dp[i][j] = max(1, min(dp[i][j+1], dp[i+1][j]) - dungeo[i][j])。

初始化

在最后一行和最后一列后面额外增加一行和一列，防止数组越界。因为在求边界时的dp时要求下面和右边的min，那么我们需要保证额外添加的部分不会影响到结果，所以需要初始化为INT_MAX。

还需要注意dp表最后一行的最后一列，他求dp时会求范围之外的两个值的dp，为了不影响结果，我们需要将这两个位置初始化为1（下边红色部分）

填表顺序

求dp[i][j]时需要有dp[i+1][j]和dp[i][j+1]，所以这题需要和前面反着来。从右向左，从下到上的顺序填表。

总结

1.状态表示：从[i][j]位置到达终点所需的最少健康点数
2.推导状态转移方程：dp[i][j] = max(1, min(dp[i][j+1], dp[i+1][j]) - dungeo[i][j])
3.初始化：在最后一行最后一列后额外添加一行一列，除了两个特殊位置为1，其他初始化为INT_MAX
4.填表：从右向左，从下向上填表
5.返回值：返回dp[0][0]。

题解：

class Solution 
{
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) 
    {
        int n = dungeon.size();
        int m = dungeon[0].size();

        //创建dp表
        vector<vector<int>> dp(n+1, vector<int>(m+1, INT_MAX));
        dp[n][m-1] = dp[n-1][m] = 1;

        //填表
        for (int i = n - 1; i >= 0; i--)
            for (int j = m - 1; j >= 0; j--)
                dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]);

        //返回结果
        return dp[0][0];
    }
};

这题困难的点就在于，我们常用的状态表示（以i为结尾的方式）不适用了，我们要有逆向思维，正着不行就反着来，想清楚后其实发现这道题也不难。

原文地址：https://blog.csdn.net/weixin_74310945/article/details/142790176

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：部署私有仓库以及docker web ui应用
下一篇：GStreamer 简明教程（六）：利用 Tee 复制流数据，巧用 Queue 实现多线程

开发指南072-图片热点
/处理跳转： area.getAttribute('href');平台支持使用图像导航界面，例如展示如下一张图，用户点击对应位置触发对应动作。热点数据通过后台接口获取（注意处理权限，没有权限的热点不生
阅读更多2024-10-13
使用机器学习边缘设备的快速目标检测
这项机器学习研究探讨了一种低成本的边缘设备，该设备与具有计算机视觉功能的嵌入式系统集成，以提高目标检测和分类的推理时间和精度。研究的主要目标是减少推理时间并降低功耗，以支持一个竞技型类人机器人的嵌入式
阅读更多2024-10-13
【Windows】【DevOps】Windows Server 2022 安装ansible，基于powershell实现远程自动化运维部署入门到放弃！
文件URL：https://www.python.org/ftp/python/3.13.0/python-3.13.0-amd64.exe。直接拿linux主机测试ansible连接windows
阅读更多2024-10-13
C# 中循环的应用说明
一循环的概念说明二、循环类型三、循环控制语句四、无限循环
阅读更多2024-10-13
Linux `vmstat` 命令详解
vmstat（Virtual Memory Statistics）是 Linux 系统中的一个监控工具，用于报告系统的虚拟内存、进程、CPU 活动等信息。它能帮助用户了解系统的整体性能状况，尤其是内存
阅读更多2024-10-13
Linux下多任务编程（网络编程2）
本文介绍解决accpet和recv相互阻塞的问题，可以用多线程并发外也可以用epoll I/O多路复用的方式解决。
阅读更多2024-10-13
[单master节点k8s部署]37.微服务（一)springCloud 微服务
微服务架构的一个重要特点是，它与开发中使用的具体或无关。每个微服务都可以使用最适合其功能需求的语言或技术来实现。例如，一个微服务可以用Java编写，另一个微服务可以用Python、Go、Node.js
阅读更多2024-10-13
Zynq(3)使用外设MIO/EMIO
使用MIO/EMIO实现流水灯，着重介绍Zynq IP核的配置，解读vitis中的c语言程序，介绍MIO与EMIO的区别。
阅读更多2024-10-13
笔试算法总结
思路很简单，但是当时做题提交的时候，通过率总是18%。不知道为啥，后面我改成了Long类型，然后就通过了全部用例。（易错1：第一次提交没考虑0的情况）使用 StringBuilder 模拟栈的行为，通
阅读更多2024-10-13
快速学习一个算法，Transformer模型架构
它的主要思想是在同一时间通过多个独立的注意力头（Attention Head）来关注序列中不同部分的信息，然后将这些信息综合起来，生成更丰富的表示。自注意力机制的目的是对输入序列中的每个元素计算一个输
阅读更多2024-10-13

一文带你掌握动态规划（一）

1. 什么是动态规划

2. 动态规划的步骤

3. 动态规划的应用

4. 动态规划的例题

4.1 简单动态规划

4.1.1 泰波那契数

4.1.2 三步问题

4.1.3 使用最小花费爬楼梯

4.1.4 解码方法

4.2 路径问题

4.2.1 不同路径

4.2.2 珠宝的最高价值

4.2.3 下降路径最小和

4.2.4 地下城游戏

相关文章