动态规划-路径问题——931.下降路径最小和

1.题目解析

题目来源：931.下降路径最小和——力扣

测试用例

2.算法原理

1.状态表示

我们可以开辟一个dp表，多开辟一行两列用来存储虚拟位置，dp[i][j]表示从第一行到该位置的最小路径和

2.状态转移方程

由于要找到最小路径和，并且由题目可以知道每一个位置的只能向下移动到下一行中相距最近的三个位置之一，由此可以得到状态表示方程为某个位置的最小路径=上面一行三个最近位置距离和+最小值与当前节点本身的值，代码表示为：dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1])+matrix[i-1][j-1]

3.初始化

上面讲到开辟了一行两列用作虚拟位置的存储，这里就需要对他们进行初始化，开辟虚拟位置的原因是在初始化dp表时边界节点需要使用到上一行相距的三个节点，所以为了避免越界就需要多开辟来使边界节点初始化更加简洁，并且要注意虚拟位置不能干扰节点的正常运算

这里第一行设置为0是保证dp表数据部分第一行的初始化不被影响且不会越界初始化，两列设置为INT_MAX是保证边界节点进行状态转移方程的运算在使用到虚拟位置时不会干扰正常运算

4.填表顺序

这里需要从上向下填表，每一行需要从左向右 

5.返回值

最后一行存储的就是到最后一行的某个节点最小路径和，这里从最后一行取出最小值就是代表整个方阵的最小路径和 

3.实战代码

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        int n = matrix.size();
        //多开辟一行两列，并且初始化为INT_MAX
        vector<vector<int>> dp(n+1,vector<int>(n+2,INT_MAX));

        //将第一行虚拟位置初始化为0
        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(dp[n][j],ret);
        }

        return ret;
    }
};