DP[dynamic programming]问题汇总分析解答（二）

矩阵DP

这一类的DP问题个人觉得是比较简单的一类，基本方法归结为下：

1.明确dp[i][j]位置代表的内容，可以为到当前为止的累加和；当前位置的方法总数等等

2.明确当前的（i,j）位置可由之前的哪一种状态变化而来，例如很多矩阵情况下会限定向下或者向右走。

3.明确上述几点之后我觉得没什么好说的了，注意边界的处理即可，往往是最上一行及最左一列

4.还有一点和之前的两个序列不同的是，现在要求的是最终位置时的值，因此返回结果为dp[row-1][col-1]

下面碰到的几道我觉得都差不多

1.leetcode 62. Unique Paths

如上所说，既然限定了左上的起点以及右下的终点，并且限定了向下以及向右走，那么毫无疑问的，递推关系为dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。剩下的就是边界的处理，处理最上一行以及最左一列，没有疑问，此时dp[0][j]和dp[i][0]的值应该为1。

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

这题其实也是凑巧，直接排列组合即可

例如m*n的位置（假设n是小的那个，如果不确定，我们首先要取小的那个），那代表向右总要要走m-1次，向下总共要走n-1次，那么排列这些走的方式，最终应该是：

class Solution {
public:
int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)return  1;
        int total = m + n - 2, small = (m < n)? m - 1: n - 1;
        unsigned long long numerator = small, denominator = total;
        while(small > 1){denominator *= --total; numerator *= --small;}
        return denominator/numerator;
    }
};

 2.leetcode 63. Unique Paths II

其他不废话了，此时多个障碍物，那么遇到vec中为1的情况，dp[i][j]直接置0即可；其余一点需要改变的是，初始值的处理，在初始行和列中但凡有一个vec中状态为1，dp中之后位置全部置0

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int row=obstacleGrid.size(),col=obstacleGrid[0].size();
        vector<vector<int>> dp(row,vector<int>(col,0));
        //initialize the dp vector
        for(int i=0;i<row;++i){
            if(obstacleGrid[i][0]==1)
                break;
            else
                dp[i][0]=1;
        }
        for(int j=0;j<col;++j){
            if(obstacleGrid[0][j]==1)
                break;
            else
                dp[0][j]=1;
        }
        for(int i=1;i<row;++i)
            for(int j=1;j<col;++j)
                dp[i][j]=obstacleGrid[i][j]==1?0:(dp[i-1][j]+dp[i][j-1]);
        return dp[row-1][col-1];
    }
};

3. leetcode 64 Minimum Path Sum

就是前面提到过的，当前存储累加和，而不是可行数。其他完全一样

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

4.leetcode120. Triangle 

个人建议从下往上进行处理，初始化时候只要最下一行即可，否则多两条斜边，懒得处理。

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle){
        vector<vector<int>> dp=triangle;
        for(int row=dp.size()-2;row>=0;--row){
            for(int col=0;col<dp[row].size();++col)
                dp[row][col]+=min(dp[row+1][col],dp[row+1][col+1]);
        }
        return dp[0][0];
    }
};

未完待续