动态规划(路径问题) 力扣 c++_c++路径最小 动态规划

120. 三角形最小路径和

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

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
思路：转换成一个二维数组，当前位置dp[i][j]得路径和之和与dp[i-1][j]、dp[i-1][j-1]有关。第一列的元素需要特殊处理，只与它的上一个位置有关，对角线上的值只与上一个对角线上的值有关。
解法1：

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int len=triangle.size();
        vector<vector<int>> dp(len,vector<int>(len,0));
        dp[0][0]=triangle[0][0];
        for(int i=1;i<len;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-1],dp[i-1][j])+triangle[i][j];
            }
            // i==j
            dp[i][i]=dp[i-1][i-1]+triangle[i][i];
        }
        return *min_element(dp[len-1].begin(),dp[len-1].end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

解法2：
dp数组当前值只与上一行的值有关，故可以用滚动数组来代替二维动态数组，代码如下：

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int len=triangle.size();
        vector<int> dp(len,0);
        dp[0]=triangle[0][0];
        for(int i=1;i<len;i++)
        {
            int prev=dp[0];
            dp[0]+=triangle[i][0];
            for(int j=1;j<i;j++)
            {
                int temp=dp[j];
                dp[j]=min(prev,dp[j])+triangle[i][j];
                prev=temp;
            }
            dp[i]=prev+triangle[i][i];
        }
        return *min_element(dp.begin(),dp.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

64. 最小路径和

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

说明：每次只能向下或者向右移动一步。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
思路：是求左上角和右下角之间的最小和，且每次只能向下或者向右移动一步，不存在走过重复位置，我们用一个二维数组记录走到当前位置的路径和，我们先初始化第一列和第一行的数据，然后dp[i][j]的与dp[i-1][j]、dp[i][j-1]和grid[i][j]有关，求的是最小路径和，所以dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
       if(grid.size()==0) return 0;
       int rows=grid.size();
       int cols=grid[0].size();
       vector<vector<int>> dp(rows,vector<int>(cols,0));
       dp[0][0]=grid[0][0];
       for(int i=1;i<rows;i++)
            dp[i][0]=dp[i-1][0]+grid[i][0];
        for(int j=1;j<cols;j++)
            dp[0][j]=dp[0][j-1]+grid[0][j];
        // 处理其他行和列的数据
        for(int i=1;i<rows;i++)
        {
            for(int j=1;j<cols;j++)
            {
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[rows-1][cols-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
输入：m = 3, n = 7
输出：28
思路1：这题可以转化为排列组合，一共需要走m+n-2步，其中m-1步是往下走的，按照组合解决问题。

class Solution {
public:
    int uniquePaths(int m, int n) {
        //用排列组合来解决问题
        if(m<1||n<1)
            return 0;
        int total = m+n-2;
        int down = m-1;
        int right=n-1;
        //计算组合时使用long类型来避免溢出
        long res=1;
        for(int i=1;i<=down;i++)
        {
            res = res*(total-down+i)/i;
        }
        return (int)res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路2：按照动态规划的思想看待问题，当前位置的走法只能是它左边方格或者它上边位置走过来的，则有dp[i][j]=dp[i-1][j]+dp[i][j-1]

class Solution {
public:
    int uniquePaths(int m, int n) {
        //用动态组合来解决问题
        vector<vector<int>> dp(m,vector<int>(n,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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

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

网格中的障碍物和空位置分别用 1 和 0 来表示。
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

思路：当前位置的走法只能是它左边方格或者它上边位置走过来的，则有dp[i][j]=dp[i-1][j]+dp[i][j-1]，与上题不同的是我们需要判断当前位置是都可通行。这题还需要特判，如果左上角或者右下角是不可通行的这代表机器人是不可以通行的，第一行和第一列只能表示一条路径上的一部分，具体代码如下所示。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int rows=obstacleGrid.size();
        int cols=obstacleGrid[0].size();
        if(obstacleGrid[0][0]==1||obstacleGrid[rows-1][cols-1]==1)
            return 0;
        vector<vector<int>> dp(rows,vector<int>(cols,0));
        dp[0][0]=1;
        for(int i=1;i<rows;i++)
        {
            if(obstacleGrid[i][0]==0)
                dp[i][0]=dp[i-1][0];
        }
        for(int j=1;j<cols;j++)
        {
            if(obstacleGrid[0][j]==0)
                dp[0][j]=dp[0][j-1];
        }
        for(int i=1;i<rows;i++)
        {
            for(int j=1;j<cols;j++)
            {
                if(obstacleGrid[i][j]==0)
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[rows-1][cols-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30