【动态规划】lettcode120 三角形最小路径和

69 阅读 0 评论 46 点赞

我是靠谱客的博主斯文斑马，最近开发中收集的这篇文章主要介绍【动态规划】lettcode120 三角形最小路径和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

：

首先记住：动态规划问题，最重要的就是找到状态转移方程，而状态转移方程很重要的一点就是明确函数的意义所在，以及记录结果的数据结构。

我们从上往下想，对于第一层的结点[0][0]它与第二层相邻的结点是[1][0],[1][1]

对于第二层的结点[1][0]它与第三层相邻的结点是[3][0],[3][1]

对于第i层的结点[i][j]它与第i+1层相邻的结点是[i+1][j]，[i+1][j+1]

即F(i,j) = Math.min(F(i+1,j),F(i+1,j+1));

上式即为解决这道问题的核心：状态转移方程! 对于动态规划而言是自低向上、递归是自顶向下。

下面则是根据状态方程写出的代码：

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        if(n == 0)
            return 0;
        
        for(int i = n-2 ; i>=0 ; i--)
            for(int j=0 ; j<triangle.get(i).size(); j++ ){
            //使用状态转移方程对从下到第i行第j列求最小值
               triangle.get(i).set(j,(int)Math.min( 
                      triangle.get(i+1).get(j),triangle.get(i+1).get(j+1))+triangle.get(i).get(j));
            }
        
        return triangle.get(0).get(0);
    }
}

无论是学习动态规划还是递归，我们总是想清清楚楚了解整个过程，实际上这是一个思维误区。当我们想想着递归的一步步过程，一层层的往下递归结果就是把自己绕进去。

你可以试着这样去理解，对于问题A，他可以分成问题B、C，你就假设B、C问题已经解决了，这时你只需要去考虑在B、C之上去解决问题。不要再去想B、C的具体过程也许就能好很多。