【OJ】动归练习三

个人主页 ： zxctscl
如有转载请先通知

1. LCR166. 珠宝的最高价值

1.1 分析

1. 状态表示
   以[i][j]位置为结尾，表示到达[i][j]位置时，此时的最大价值。

2. 状态转移方程
   要在[i][j]位置时候得到最大价值，要么从它上面的一个下来，要么从它左边一个过来，但是选择的是价值更大的那一个,再加上它本身那一个所对应的价值
   dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i][j]

3. 初始化
   这里也是要涉及到可能会越界问题，就直接多开一行和一列，为了不影响价值计算的结果就全部都初始化为0。这里得注意下标的映射，此时在dp[i][j]位置就对应frame[i-1][j-1]，写代码时候得注意。
   

4. 填表顺序
   从上往下，从左往右

5. 返回值
   直接返回dp[m][n]就行
   

1.2 代码

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
      int m=frame.size();
      int n=frame[0].size();
      vector<vector<int>> dp(m+1,vector<int> (n+1));
    
      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];

    }
};

2. 931.下降路径最小和

2.1 分析

1. 状态表示
   同样是以[i][j]位置结尾，来找下降路径的最小和。

2. 状态转移方程

想要到达[i][j]位置有三种方式[i-1][j-1]和[i-1][j]还有[i-1][j+1]，

而题目要求的是最小和，那么就取这三个位置的最小值和，再加上这个位置本身的值

3. 初始化
   像绿色星号标注的位置可能会存在越界的问题，所以就多开两列和一行。但是想让填表时候第一行位置所在的值不变，那么新开空间的第一行就初始化为0：
   
   但如果也把左边开的这一列初始化为0，那么红色格子这格的最小值和可能就会用到这个0，所以这里不能写0，为了不改变选择的结果，就把这些初始化为INT_MAX

4. 填表顺序
   从上往下

5. 返回值
   返回最后一行最小的值
   

2.2 代码

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
     int n=matrix.size();
     vector<vector<int>> dp(n+1,vector<int> (n+2,INT_MAX));
     for(int j=0;j<n+2;j++)dp[0][j]=0;

     for(int i=1;i<=n;i++)
     {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=min(dp[i-1][j-1],min(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[n][j]);

    return ret;
    }
};

3. 64.最小路径和

3.1 分析

1. 状态表示
   以[i][j]为结尾，找最小和。
   dp[i][j]表示到达[i][j]位置时，最小路径和。

2. 状态转移方程
   根据最近的一步划分问题。
   到到达[i][j]位置有两种方式，一种从上面，一种从左边
   
   一种是以最小的路径到上面，然后加上当前位置的值；
   另一种是最小的路径到左边，然后加上当前位置的值。
   
   所以到达的dp[i][j]最小值就是，两种中取最下的那一个
   

3. 初始化
   这里可能会存在越界访问的情况，所以多开一行和一列。但要注意里面填的值，要保证在后面计算的结果是正确的。
   第一行第一列为了值不被改变，就得在新开空间的上面一格和左边一格的值为0，其他的为了不影响后面取最小值和的计算，都初始化为INT_MAX
   

4. 填表顺序
   从上往下，从左往右

5. 返回值
   要求每个位置的最小值，就直接返回dp[m][n]
   

3.2 代码

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]=dp[1][0]=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];
    }
};

有问题请指出，大家一起进步！！！