三角形最小路径和

1. 动态规划

      2
     3 4
    6 5 7
   4 1 8 3

题是这样的一次只能走一步，然后求出最短的路径，看到这道题很多人第一反应，双重循环分别去比较每个数的大小，这个思路很不错，让我们在多想一点点，那就是如果双重循环的话就会产生很多次重复的计算，就像斐波那契数列一样如果用普通的遍历，或者是递归计算的话，一般计算机在计算到50的时间计算任务应该是指数级别的增长，假如我们拿出一个数组来记录一下他每次计算的值，这样是不是就省去了好多不必要的计算，同样这道题也可以这样想，我们把计算的结果记录下来这样就避免了重复的计算，这就是动态规划的精华所在。

• 我们思考几个点，想要计算使用动态规划来解这道题，我们首先看一下这道题有啥规律，经过观察我们发现，假设i是行j是列，第一行只有一个元素的时候我们只能往下走，意思就是i+1第二行就有了两个元素，我们可以选择i+1或者是j+1这种情况，我们观察发现递推公式dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+value这样的公式。

• 通常我们解决问题，从下向上解题是比较简单的，所以我们循环的起始下标就为len(array),这样准备好所有条件好我们来看一下具体的go语言代码实现：

func Min(i, j int) int {
  if i < j {
    return i
  }
  return j
}
func minimumTotal(triangle [][]int) int {
  var dp = make([][]int, len(triangle)+1) //创建一个跟三角形外环一样长度的数组
  for i := 0; i < len(triangle)+1; i++ { //因为go语言特性，我们需要给二维数组赋值
    dp[i] = make([]int, len(triangle)+1)
  }
  for i := len(triangle) - 1; i >= 0; i-- {
    for j := 0; j <= i; j++ {
      dp[i][j] = Min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
    }
  }
  return dp[0][0] //返回最小路径
}

上面就是动态规划的解法，时间复杂度在On2,由于使用记忆数组，使得减少了很多的计算量，在实际表现上来看还是不错的。