抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

46 | 面试题:三角形的最小路径和

120. 三角形最小路径和

解法一:回溯

走所有的路径,计算每条路径的和,再判断最小值。

时间复杂度:O( 2^n )

解法二:动态规划

  1. 状态的定义:从下往上推,定义DP[ i , j ],存储从最下面的节点走到[ i , j ]这个点的路径和最小值。[ 0 , 0 ]点为最终结果。
  2. DP方程:DP[ i , j ] = min( DP[ i + 1 , j ] , DP[ i + 1 , j + 1] ) + Triangle[ i , j ]

对于最下面的一行,就是节点本身了。所以 DP[ m – 1 , j ] = Triangle[ m – 1 , j ]

时间复杂度 O( m * n )

代码:

这里需要想明白递推公式,为什么要从下往上递推。以及优化的点,为什么只需要最后一行大小的数组即可。

详细题解:https://leetcode-cn.com/problems/triangle/solution/zi-di-xiang-shang-dong-tai-gui-hua-lei-si-yu-cong-/

class Solution {
    fun minimumTotal(triangle: List<List<Int>>): Int {

        val mini = triangle[triangle.size - 1].toIntArray()
        for (i in triangle.size - 2 downTo 0)
            for (j in triangle[i].indices) {
                mini[j] = triangle[i][j] + Math.min(mini[j], mini[j + 1])
            }
        return mini[0]
    }
}


0条评论

发表评论