使用 dp[i][j] 存储走到i,j时 总可能的路径数
因为只可以向下向右走，则任意点的路径数为dp[i][j] = dp[i-1][j] + dp[i][j-1];
dp初始化最上面一排和最左面一排，因为只可以向右走和向下走，所以初始化路径数都为1，其它为0

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++)
            {
                if( i==0 || j==0)
                    dp[i][j] = 1;
                else
                    dp[i][j] = 0;
            }
        }

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

63. 不同路径II


状态转移方程跟上题一样，不同的是 初始化需要改变，以及如果dp[i][j]的上一步中存在障碍，则舍弃那条路的可能路径数

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    if(!obstacleGrid.size() || !obstacleGrid[0].size()) return 0;

    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    long dp[m][n];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++)
        {
            if(i==0 && j==0){
                if(obstacleGrid[i][j]==0) dp[i][j]=1;
                else dp[i][j]=0;
            }
            else if(i==0)  {
                if( obstacleGrid[i][j]==0) dp[i][j] = dp[i][j-1];
                else dp[i][j]=0;
            }
            else if(j==0)  {
                if( obstacleGrid[i][j]==0) dp[i][j] = dp[i-1][j];
                else dp[i][j]=0;
            }
        }
    }

    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            if(obstacleGrid[i][j]==1) dp[i][j]=0;
            else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    return dp[m-1][n-1];
}

64. 最小路径和

很典型的DP题，只需要注意初始化皆可以
dp[i][j] 存储走到i,j点时，当前的路径和
因为只有两个方向走，所以任意点的最小路径和，为上两个点的最小路径和加上当前点的权重 dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);

int minPathSum(vector<vector<int>>& grid) {
        if(!grid.size() || !grid[0].size()) return 0;
        int m = grid.size();
        int n = grid[0].size();
        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 i=1;i<n;i++) dp[0][i] = dp[0][i-1]+grid[0][i];
        
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
            }
        }
        return dp[m-1][n-1];
    }

139. 单词拆分


使用dp[i] 表示字符串第i个位置之前的子字符可拆分出来
所以任意点的状态为 dp[i+j] = dp[i] && m.find(s.substr(i,j))!=m.end(),即第i个字符可拆分，且i-j之前的子字符也可拆分，此时就更新dp[i+j]可拆分，dp[s.size()]记录到字符最后长度时，是否存在可拆分的路径组合

"aaaaaaa"  dice = {'aaaa','aaa'}  0-3 可拆分‘aaa’ 3-6 可拆分‘aaa’  但是最后一个‘a’ 不可拆分
								   0-4 可拆分‘aaaa’   4-7可拆分‘aaa’ 

bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1,false);
        unordered_set<string> m(wordDict.begin(), wordDict.end());
        dp[0] = true;
        
        // 从0开始，切割(1,len)长的子字符， 然后从1开始，切割(1,len-1)的子字符
        for(int i=0;i<s.size();i++){
            for(int j=1;j<=s.size()-i;j++){
                if(dp[i] && m.find(s.substr(i,j))!=m.end()){
                    dp[i+j] = true;
                }
            }
        }
        
        // 另一种切割子字符串的方式 从不同的
        // for(int i=1;i<=s.size();i++){
        // for(int j=0;j<i;j++){
        // if(dp[j] && m.find(s.substr(j,i-j))!=m.end()){
        // dp[i] = true;
        // break;
        // }
        // }
        // }


        return dp[s.size()];
    }

343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

使用dp[i] 记录数字i拆分可组合的最大乘积子和
那么任意一点的可拆分最大值为 dp[i] = dp[j] * (i-j),即所有i之前的最大乘积*(i-j)的差值, 或者是直接拆分成两个数的乘积( j* (i-j) ),因为dp[j]是已经拆分过的最大值