Leetcode-120. 三角形最小路径和（动态规划）

一时失言乱红尘 2023-02-26 04:27 108阅读 0赞

### 120. 三角形最小路径和（动态规划） ###

*  方法一：自顶向下
 *  方法二：自底向上

> 120.三角形最小路径和  
> 题目链接：[https://leetcode-cn.com/problems/triangle/][https_leetcode-cn.com_problems_triangle]

# 方法一：自顶向下 #

**第一次靠自己做出了动态规划的题，有点小开心！！  
于此记录一下第一次自主做出动态规划，就是可惜第一次多加了个Math.max没有一次pass**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyNTQ0NA_size_16_color_FFFFFF_t_70]

class Solution { 
           public int minimumTotal(List<List<Integer>> triangle) { 
            int lenX=triangle.get(triangle.size()-1).size();
            int boo[][]=new int[lenX][lenX];
            int min=Integer.MAX_VALUE;
            int dp[][]=new int[lenX][lenX];
            dp[0][0]=triangle.get(0).get(0);
            for(int i=0;i<triangle.size()-1;i++){ 
                int lenx=triangle.get(i).size();
                for (int j = 0; j <lenx; j++) { 
                    if ( boo[i+1][j]!=1) { 
                        dp[i + 1][j] = triangle.get(i + 1).get(j) + dp[i][j];
                        boo[i + 1][j] = 1;
                    }else { 
                        dp[i + 1][j] = Math.min(triangle.get(i + 1).get(j) + dp[i][j], dp[i + 1][j]);
                    }
                    if (boo[i+1][j+1]!=1) { 
                        dp[i + 1][j + 1] =triangle.get(i + 1).get(j + 1) + dp[i][j];
                        boo[i + 1][j + 1] = 1;
                    }else { 
                        dp[i + 1][j] = Math.min(triangle.get(i + 1).get(j) + dp[i][j], dp[i + 1][j]);
                    }
    
                }
            }
             for (int j=0;j<dp[dp.length-1].length;j++){ 
                min=Math.min(min,dp[dp.length-1][j]);
             }
    
             return min;
        }
    }

# 方法二：自底向上 #

再来看看大佬写的自底向上的代码，看完真的是大叫一声WoCao，太精妙了，给看哭了都

class Solution { 
        public int minimumTotal(List<List<Integer>> triangle) { 
            int n = triangle.size();
            // dp[i][j] 表示从点 (i, j) 到底边的最小路径和。
            int[][] dp = new int[n + 1][n + 1];
            // 从三角形的最后一行开始递推。
            for (int i = n - 1; i >= 0; i--) { 
                for (int j = 0; j <= i; j++) { 
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
                }
            }
            return dp[0][0];
        }
    }

作者：sweetiee  
代码出自：甜姨  
[https://leetcode-cn.com/problems/triangle/solution/di-gui-ji-yi-hua-dp-bi-xu-miao-dong-by-sweetiee/][https_leetcode-cn.com_problems_triangle_solution_di-gui-ji-yi-hua-dp-bi-xu-miao-dong-by-sweetiee]

--------------------

**持续更新中…**

[https_leetcode-cn.com_problems_triangle]: https://leetcode-cn.com/problems/triangle/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyNTQ0NA_size_16_color_FFFFFF_t_70]: /images/20230209/ed75bd835953461ebd8504c1ca275cf6.png
[https_leetcode-cn.com_problems_triangle_solution_di-gui-ji-yi-hua-dp-bi-xu-miao-dong-by-sweetiee]: https://leetcode-cn.com/problems/triangle/solution/di-gui-ji-yi-hua-dp-bi-xu-miao-dong-by-sweetiee/