写在前面

动态规划算是比较难的题目，之前遇到这种题目都不知道怎么下手，或者想到用动态规划做也做不出来。今天比赛中的第三题还没读完题目就感觉应该用动态规划做，并且在纸上稍微思考了一下就写出了动态方程和边界情况，非常顺畅，再次记录一下

6433. 矩阵中移动的最大次数

思考

这种从开始状态经过一步一步到达最终状态的问题，都是典型的动态规划问题。

假设从第i列开始到达最后一列所需要的步数为data[i]，则只需要求出data[i-1]即可；如果grid[i+1][j-1]，grid[i+1][j]，grid[i+1][j+1]有大于grid[i][j]，则data[i]=data[i-1]+1,其中data[i-1]等于grid[i+1][j-1]，grid[i+1][j]，grid[i+1][j+1]三个位置周最大的哪个。

用公式说明则为：data[i]=data[i-1]+1; 其中data[i-1]=min(data[i-1][j-1],data[i-1][j1],data[i-1][j+1]);

注意，这里用到的data是二维数组，因为当i-1的时候，有三种情况，所以需要记录这3个节点的data值

边界条件：显然当i=m-2的时候，data[i]=0或者1

基于上述分析，动态公式和边界条件都找出来了，就可以写代码实现了。

代码

func maxMoves(grid [][]int) int {
   m := len(grid)
   n := len(grid[0])
   // 定义二维数组data，data[i][j]表示从第(i,j)位置到到最右边需要移动的最大次数，初始值为0
   data := make([][]int, m)
   for i := range data {
      data[i] = make([]int, n)
   }
   maxStep := 0
   // j=n-2表示从倒数第二行开始，倒数第一列所有的data都为0
   for j := n - 2; j >= 0; j-- {
      for i := 0; i < m; i++ {
         max := -1 // max表示从data[][j]列到data[][j+1]列需要的步数
         if i-1 >= 0 && grid[i-1][j+1] > grid[i][j] {
            if data[i-1][j+1] > max {
               max = data[i-1][j+1]
            }
         }
         if grid[i][j+1] > grid[i][j] {
            if data[i][j+1] > max {
               max = data[i][j+1]
            }
         }
         if i+1 < m && grid[i+1][j+1] > grid[i][j] {
            if data[i+1][j+1] > max {
               max = data[i+1][j+1]
            }
         }
         // max表示当在(i,j)节点时data[][j+1]的值， data[i][j] = max+1是因为从i列到j列需要走一步，当max=-1的时候表示走不通，则这个时候data[i][j]=0
         data[i][j] = max + 1

         if j == 0 {
         // 当到达第一列的时候，计算最大需要移动的次数
            if data[i][j] > maxStep {
               maxStep = data[i][j]
            }
         }
      }
   }

   return maxStep
}