动态规划：路径系列

2024-01-16 09:26:22

LeetCode64. 最小路径和

https://leetcode-cn.com/problems/minimum-path-sum/

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

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

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

思路

1.思考状态：找出最优解的性质，明确状态表示什么

dp[i] [j] 表示第0行第0列走到第i行第j列的最短路径

2.思考状态转移方程：大问题的最有解如何由小问题的最优解得到

题目要求：每次只能向下或者向右移动一步，换句话说，当前单元格 (i,j) 只能从左方单元格 (i-1,j)或上方单元格 (i,j-1) 走到。

所以：dp[i] [j] = min(dp[i - 1] [j], dp[i] [j - 1]) + grid[i] [j]

3.思考初始状态

第0行上的网格只能通过向右走到达，同理，第0列上的网格只能通过向下走到达

所以：dp[0] [0] = grid[0] [0]
dp[i] [0] = dp[i - 1] [0] + grid[i] [0]
dp[0] [j] = dp[0] [j - 1] + grid[0] [j]

4.自底向上计算得到最优解

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

5.思考是否可以进行空间的优化

代码

class Solution 
{
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        int m = grid.size();
        int n = grid[0].size();
        if (m == 0 || n== 0)
        {
            return 0;
        }

        int dp[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1;i < m;++i)
        {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

         for (int j = 1;j < n;++j)
        {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

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

        return dp[m - 1][n - 1];
    }
};

LeetCode120. 三角形最小路径和

https://leetcode-cn.com/problems/triangle/

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

思路

1.思考状态：找出最优解的性质，明确状态表示什么

dp[i] [j]表示从三角形顶部即第0行第0列走到第i行第j列的最小路径和

2.思考状态转移方程：大问题的最有解如何由小问题的最优解得到

题目要求：每一步只能移动到下一行中相邻的结点上，因此要想走到位置 (i, j)，上一步就只能在位置 (i - 1, j - 1) 或者位置 (i - 1, j)。

需要注意的是处理边界情况：如果j = 0，那么要想走到位置 (i, j)，上一步就只能在位置 (i - 1, j)；如果j = i，那么要想走到位置 (i, j)，上一步就只能在位置 (i - 1, j - 1) 。

所以：dp[i] [j] = dp[i - 1] [j] + triangel[i] [j]，其中j == 0
dp[i] [j] = min{ dp[i - 1] [j], dp[i - 1] [j - 1] } + triangel[i] [j]，其中1 <= j <= i - 1
dp[i] [j] = dp[i - 1] [j - 1] + triangel[i] [j]，其中j == i

3.思考初始状态

dp[0] [0] = triangel[0] [0]

4.自底向上计算得到最优解

        for (int i = 1; i < size; ++i)
        {
            dp[i][0] = dp[i -1][0] + triangle[i][0];
            for (int j = 1; j < i; ++j)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
        }

5.思考是否可以进行空间的优化

使用一个滚动的一维数组dp[j]来表示上面的二维数组dp[i] [j]，即：

        for (int i = 1; i < size; ++i)
        {
            dp[i] = dp[i - 1] + triangle[i][i];
            for (int j = i - 1; j >= 1; --j)
            {
                dp[j] = min(dp[j], dp[j - 1]) + triangle[i][j];
            }
            dp[0] = dp[0] + triangle[i][0];
        }

应逆序遍历j，这样才能保证正确的结果。如果我们正序遍历j，那么在计算第i行第j列时，dp[0]到dp[j - 1]已经是第i行的值，而我们仍然使用上述状态转移方程，那么实际上是在dp[i] [j - 1] 和 dp[i - 1] [j] 中进行选择，就产生了错误。

代码

class Solution 
{
public:
    //动态规划
    /*int minimumTotal(vector<vector<int>>& triangle) 
    {
        int size = triangle.size();
        if (size == 0)
        {
            return 0;
        }

        vector<vector<int>> dp(size, vector<int>(size));
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < size; ++i)
        {
            dp[i][0] = dp[i -1][0] + triangle[i][0];
            for (int j = 1; j < i; ++j)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
        }

        return *min_element(dp[size - 1].begin(), dp[size - 1].end());
    }*/

    //优化动态规划
    int minimumTotal(vector<vector<int>>& triangle) 
    {
        int size = triangle.size();
        if (size == 0)
        {
            return 0;
        }

        vector<int> dp(size);
        dp[0] = triangle[0][0];
        for (int i = 1; i < size; ++i)
        {
            dp[i] = dp[i - 1] + triangle[i][i];
            for (int j = i - 1; j >= 1; --j)
            {
                dp[j] = min(dp[j], dp[j - 1]) + triangle[i][j];
            }
            dp[0] = dp[0] + triangle[i][0];
        }

        return *min_element(dp.begin(), dp.end());
    }

};

LeetCode62. 不同路径

https://leetcode-cn.com/problems/unique-paths/

一个机器人位于一个 m x n 网格的左上角

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角

问总共有多少条不同的路径？

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

思路

1.思考状态：找出最优解的性质，明确状态表示什么

dp[i] [j] 表示第0行第0列走到第i行第j列不同路径的数量

2.思考状态转移方程：大问题的最有解如何由小问题的最优解得到

题目要求：每次只能向下或者向右移动一步，换句话说，当前单元格 (i,j) 只能从左方单元格 (i-1,j)或上方单元格 (i,j-1) 走到。想要求dp[i] [j]，只能有两个方向来推导出来，即dp[i - 1] [j] 和 dp[i] [j - 1]，而 dp[i - 1] [j] 表示第0行第0列走到第i - 1行第j列不同路径的数量，dp[i] [j - 1]同理。

所以：dp[i] [j] = dp[i - 1] [j] + dp[i] [j - 1]

3.思考初始状态

因为从(0, 0)到(i, 0)的路径只有一条，所以：dp[i] [0] = 1

同理：dp[0] [j] = 1

4.自底向上计算得到最优解

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

5.思考是否可以进行空间的优化

使用一个滚动的一维数组dp[j]来表示上面的二维数组dp[i] [j]，即：

        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                dp[j] = dp[j] + dp[j - 1];
            }
        }

代码

class Solution 
{
public:
    //动态规划
    /*int uniquePaths(int m, int n) 
    {
        int dp[m][n];
        for (int i = 0; i < m; ++i)
        {
            dp[i][0] = 1;
        }
        for(int j = 0; j < n; ++j)
        {
            dp[0][j] = 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 - 1][n - 1];
    }*/

    //优化
    int uniquePaths(int m, int n)
    {
        vector<int> dp(n, 1);
        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                dp[j] = dp[j] + dp[j - 1];
            }
        }

        return dp[n - 1];
    }
};

LeetCode63. 不同路径II

https://leetcode-cn.com/problems/unique-paths-ii/

一个机器人位于一个 m x n 网格的左上角

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

思路

1.思考状态：找出最优解的性质，明确状态表示什么

dp[i] [j] 表示第0行第0列走到第i行第j列不同路径的数量

2.思考状态转移方程：大问题的最有解如何由小问题的最优解得到

状态转移方程和Leetcode62. 不同路径(见上文)一样：dp[i] [j] = dp[i - 1] [j] + dp[i] [j - 1]。

但这里需要注意一点，因为有了障碍，所以如果(i, j)就是障碍的话应该就保持初始值0

3.思考初始状态

初始状态**和Leetcode62. 不同路径(见上文)一样：dp[i] [0] = 1, dp[0] [j] = 1

但这里需要注意一点，因为有了障碍，所以如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，即障碍之后（包括障碍）的dp[i] [0]应该还是初始值0。dp[0] [j]同理。

4.自底向上计算得到最优解

5.思考是否可以进行空间的优化

代码

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

        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (decltype(m) i = 0; i < m && obstacleGrid[i][0] == 0; ++i)
        {
            dp[i][0] = 1;
        }
        for (decltype(n) j = 0; j < n && obstacleGrid[0][j] == 0; ++j)
        {
            dp[0][j] = 1;
        }

        for (decltype(m) i = 1; i < m; ++i)
        {
            for (decltype(n) j = 1; j < n; ++j)
            {
                if (obstacleGrid[i][j] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
};

码农公寓

LeetCode64. 最小路径和

思路

代码

LeetCode120. 三角形最小路径和

思路

代码

LeetCode62. 不同路径

思路

代码

LeetCode63. 不同路径II

思路

代码

相关文章