【动态规划】路径问题

简介: 【动态规划】路径问题

动态规划(路径问题)

1. 不同路径 |

题目链接

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

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. 不同路径 ||

题目链接

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

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

  1. 初始化
    初始化,仍然采用辅助节点的方式
  1. 填表
    从上到下,从左到右
  2. 返回值

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. 礼物的最大价值

题目链接

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

  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. 下降最小和

题目链接

  1. 状态表示
    dp[i][j]表示到i, j 位置时的最小和
  2. 状态转移方程

  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. 最小路径和

题目链接

  1. 状态表示
    dp[i][j]表示i, j 位置时,最小的路径和
  2. 状态转移方程

  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. 地下城游戏

题目链接

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

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];
    }
};
相关文章
|
7月前
|
算法
算法修炼-动态规划之路径问题(1)
算法修炼-动态规划之路径问题(1)
|
4月前
|
算法 Java
二叉树路径与回溯法
文章通过LeetCode第257题"二叉树路径"的解题过程,详细阐述了如何利用前序遍历和回溯法来找出二叉树中所有从根节点到叶子节点的路径,并提供了Java语言的代码实现,强调了回溯法在解决类似问题中的重要性。
二叉树路径与回溯法
|
6月前
|
算法 C++
【动态规划】零基础解决路径问题(C++)
【动态规划】零基础解决路径问题(C++)
|
算法 机器人
【学会动态规划】不同路径(5)
【学会动态规划】不同路径(5)
62 1
|
7月前
|
机器人
动态规划|【路径问题】63.不同路径II
动态规划|【路径问题】63.不同路径II
|
7月前
|
算法 机器人 BI
动态规划|【路径问题】|62.不同路径I
动态规划|【路径问题】|62.不同路径I
|
7月前
leetcode-124. 二叉树中的最大路径和
leetcode-124. 二叉树中的最大路径和
36 0
|
算法
【学会动态规划】不同路径 II(6)
【学会动态规划】不同路径 II(6)
53 0
|
机器人
【动态规划刷题 3】不同路径&&不同路径 II
【动态规划刷题 3】不同路径&&不同路径 II