【动态规划】路径问题

忘是亡心i 2024-03-22 20:36 137阅读 0赞

#### 文章目录 ####

*  动态规划（路径问题）
 *   *  1. 不同路径 |
     *  2. 不同路径 ||
     *  3. 礼物的最大价值
     *  4. 下降最小和
     *  5. 最小路径和
     *  6. 地下城游戏

## 动态规划（路径问题） ##

### 1. 不同路径 | ###

[题目链接][Link 1]

1.  状态表示
    
    `dp[i][j]` 表示以i，j为结尾的时候，有多少中路径
2.  状态转移方程
    
    ![eo42wp02n9-1690264886368.png][]
3.  初始化
    
    初始化的地方采用虚拟节点的办法。辅助节点里面的值要保证后续的填表是正确的，并且下标的映射关系要正确
    
    ![0mqx2i8i3i-1690265248365.png][]
    
    这里必须保证阴影部分有一个地方为1，这样就能保证初始化是正确的
4.  填表
    
    从上到下，从左到右
5.  返回值

AC代码：

class Solution 
    {
        
    public:
        int uniquePaths(int m, int n) 
        {
        
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
            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];
        }
    };

### 2. 不同路径 || ###

[题目链接][Link 2]

1.  状态表示
    
    `dp[i][j]`表示到i, j 位置有多少种路径
2.  状态转移方程
    
    ![mzuzkj77ad-1690265644328.png][]

如果是障碍物，不需要处理这个节点位置，

1.  初始化
    
    初始化，仍然采用辅助节点的方式
    
    ![rlj0rpbzyw-1690265822334.png][]
2.  填表
    
    从上到下，从左到右
3.  返回值

AC代码：

class Solution 
    {
        
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
        {
        
            int m = obstacleGrid.size(), n = obstacleGrid[0].size();
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
            dp[0][1] = 1;
            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];
        }
    };

### 3. 礼物的最大价值 ###

[题目链接][Link 3]

1.  状态表示
    
    `dp[i][j]`表示到i， j位置时最大的价值
2.  状态转移方程

![uvlij1bjos-1690265983442.png][]

1.  初始化
    
    仍然采用虚拟节点的方法，来初始化。这里只需要将虚拟节点里面的值都初始化为0即可
2.  填表
    
    从上到下，从左到右
3.  返回值

AC代码：

class Solution 
    {
        
    public:
        int maxValue(vector<vector<int>>& grid) 
        {
        
            int m = grid.size(), n = grid[0].size();
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
            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]) + grid[i - 1][j - 1];
                }
            }
            return dp[m][n];
        }
    };

### 4. 下降最小和 ###

[题目链接][Link 4]

1.  状态表示
    
    `dp[i][j]`表示到i， j 位置时的最小和
2.  状态转移方程
    
    ![973k1n454g-1690266352443.png][]
3.  初始化
    
    这里虚拟节点，需要加一行再加上两列
4.  填表
    
    从上往下，从左到右
5.  返回值
    
    最后一行的最小值

AC代码：

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

### 5. 最小路径和 ###

[题目链接][Link 5]

1.  状态表示
    
    `dp[i][j]`表示i， j 位置时，最小的路径和
2.  状态转移方程
    
    ![o8t5vmkatt-1690266898443.png][]
3.  初始化
    
    虚拟节点，方便初始化
4.  填表
5.  返回值

AC代码：

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

### 6. 地下城游戏 ###

[题目链接][Link 6]

1.  状态表示
    
    如果当以i, j 位置结尾所需的最低健康点数，为状态表示的时候，后面的节点也会影响这个节点的值。所以以某个位置为结尾的时候不能很好的解决这个题目。换一个状态表示：
    
    如果以`i, j`为开始到达终点的所需健康点数，就可以很好的解决这个题目
2.  状态转移方程
    
    ![jm1pc5rhoc-1690267311444.png][]

`dp[i][j] + d[i][j] >= dp[i][j + 1]`，需要注意的是当是一个负数的时候需要改为1

1.  初始化
2.  填表
    
    从下往上，从右到左
3.  返回值

AC代码：

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][j + 1], dp[i + 1][j]) - dungeon[i][j];
                    dp[i][j] = max(1, dp[i][j]);
                }
            }
            return dp[0][0];
        }
    };

[Link 1]: https://leetcode.cn/problems/unique-paths/
[eo42wp02n9-1690264886368.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/06800ac9315346fc9753615424fb9a6b.png
[0mqx2i8i3i-1690265248365.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/1efddfceef014b188e7ec50fced609af.png
[Link 2]: https://leetcode.cn/problems/unique-paths-ii/
[mzuzkj77ad-1690265644328.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/4006e36faa8540ecaac31c37ef282fa8.png
[rlj0rpbzyw-1690265822334.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/703faa4bde4748f29ff52cc449552ade.png
[Link 3]: https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/
[uvlij1bjos-1690265983442.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/3efcb40dd5224f5fbb86dfc6fc8425cd.png
[Link 4]: https://leetcode.cn/problems/minimum-falling-path-sum/
[973k1n454g-1690266352443.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/6a04a8506f384afa860e62d752e60af0.png
[Link 5]: https://leetcode.cn/problems/minimum-path-sum/
[o8t5vmkatt-1690266898443.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/bc72b524c76445359bf905854a91c08d.png
[Link 6]: https://leetcode.cn/problems/dungeon-game/
[jm1pc5rhoc-1690267311444.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8319825f0870405ba882a649392758a3.png