下降路径问题

931. 下降路径最小和

给你一个n x n的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径的最小和。
下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：下面是两条和最小的下降路径，用加粗+斜体标注：
[[2,1,3],      [[2,1,3],
 [6,5,4],       [6,5,4],
 [7,8,9]]       [7,8,9]]

解決这类问题我们可以自上而下的来解决问题：找当前层的最小值，那么就要把当前层的最小值的上方来按照对应的规则来递推前一层的最小值,如此类推循环到最后一层,

func minFallingPathSum(matrix [][]int) int {
    ans:=math.MaxInt32
    for i:=1;i<len(matrix);i++{
        for j:=0;j<len(matrix);j++{
            if j==0{
                matrix[i][j]+=min(matrix[i-1][0],matrix[i-1][j+1])
            }else if j==len(matrix)-1{
                matrix[i][j]+=min(matrix[i-1][j-1],matrix[i-1][j])
            }else{
                matrix[i][j]+=min(matrix[i-1][j+1],min(matrix[i-1][j-1],matrix[i-1][j]))
            }
        }
    }
    for i:=0;i<len(matrix);i++{
        ans=min(ans,matrix[len(matrix)-1][i])
    }
    return ans
}
func min(a,b int)int{
    if a>b{
        return b
    }
    return a
}

120. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标+ 1 的两个结点。也就是说，如果正位于当前行的下标 i，那么下一步可以移动到下一行的下标 i 或 i + 1 。

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

三角形下降也是同样的道理，只不过规则的选取变成了当前行 ↓ ↘ 那么我们从当前层往上找，难道就是取得 ↑ ↖

func minimumTotal(triangle [][]int) int {
    if len(triangle)==0{
        return 0
    }
    if len(triangle)==1{
        return triangle[0][0]
    }
    ans:=math.MaxInt32
    for i:=1;i<len(triangle);i++{
        for j:=0;j<=i;j++{
            if j==0 {
                triangle[i][j]+=triangle[i-1][j]
            }else if j==i{
                triangle[i][j]+=triangle[i-1][j-1]
            }else{
                triangle[i][j]+=min(triangle[i-1][j-1],triangle[i-1][j])
            }
        }
    }
     for i:=0;i<len(triangle);i++{
         ans=min(ans,triangle[len(triangle)-1][i])
     }
     return ans
}
func min(a,b int)int{
    if a>b{
        return b
    }
    return a 
}