动态规划问题 -- 路径模型（下降路径最小和）

动态规划分析问题五步曲

不清楚动态规划分析问题是哪关键的五步的少年们可以移步到
链接: 动态规划算法基础
这篇文章非常详细的介绍了动态规划算法是如何分析和解决问题的

题目概述

链接: 下降路径最小和

1. 状态表示（题目要求+自己的经验）
   本题状态dp[i][j] ：表示到第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表1行和2列
   为了防止选择无意义的值，把其初始化为 0x3f3f3f3f （在动态规划中，0x3f3f3f3f是一个足够大的无意义值）

4. 填表顺序（分析要填i位置前一个依赖状态的位置）
   dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1])) + matrix[i-1][j-1]
   显然是从上到下填表（从左到右和从右到左无所谓）

5. 返回值（由题目要求来）
   由于我们可以从网格底部的任意单元方格出这个网格，所以应该返回所有底部网格的最小值

代码编写

有了动态规划五步曲我们就可以写出非常优雅的代码了

int minFallingPathSum(vector<vector<int>>& matrix) {int defaults = 0x3f3f3f3f;int m = matrix.size() , n = matrix[0].size();vector<vector<int>> dp(m+1,vector<int>(n+2));for(int i = 1 ; i <= m ; i++)dp[i][0] = dp[i][n+1]  = defaults;for(int i = 1 ; i <= m ; 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[m][j]);return ret;}

少年，今天你又进步了一点点哟，明天继续加油吧