DP：路径规划模型

class Solution {
public:
    int uniquePaths(int m, int n) 
    {
       vector<vector<int>>  dp(m+1,vector<int>(n+1));//创建一个有辅助节点的数组
       //初始化dp[0][1]画图去理解
       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];
    }
};

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));//创建一个dp数组
        //初始化dp[0][1]
        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];
    }
};

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) 
    {
        int m=frame.size(),n=frame[0].size();
        vector<vector<int>>  dp(m+1,vector<int>(n+1));//创建一个dp数组
        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])+frame[i-1][j-1];
                return dp[m][n];
    }
};

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

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
       int m=matrix.size(),n=matrix[0].size();
       vector<vector<int>> dp(m+1,vector<int>(n+2,INT_MAX));//加一行，多加两列，两列得是INT MAX
       for(int j=0;j<n+2;++j) dp[0][j]=0;//第一行初始化成0
       for(int i=1;i<=m;++i)
         for(int j=1;j<=n;++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<=n;++j) ret=min(ret,dp[m][j]);
       return ret;
    }
};

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-1][n]=1;
      for(int i=m-1;i>=0;--i)
       for(int j=n-1;j>=0;--j)
        {
          int mini=min(dp[i+1][j],dp[i][j+1]);
          dp[i][j]=max(mini-dungeon[i][j],1);//要防止出现大血包
        }
        return dp[0][0];
    }
};