• 120.三角形最小路径和


    三角形最小路径和

    递归视频讲解

    给定一个三角形 triangle ,找出自顶向下的最小路径和。
    
    每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。
    
     
    
    示例 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)。
    示例 2:
    
    输入:triangle = [[-10]]
    输出:-10
     
    
    提示:
    
    1 <= triangle.length <= 200
    triangle[0].length == 1
    triangle[i].length == triangle[i - 1].length + 1
    -104 <= triangle[i][j] <= 104
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    解法一:
    递归:

    class Solution {
    public:
        int minroad(int i, int j, vector<vector<int>> triangle){
            if (i == triangle.size() - 1){
                return triangle[i][j];
            }
            int x = minroad(i + 1, j, triangle);
            int y = minroad(i + 1, j + 1, triangle);
            return min(x, y) + triangle[i][j];
    
        }
        int minimumTotal(vector<vector<int>>& triangle) {
    
            int result = minroad(0, 0, triangle);
            return result;
    
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    超时,存在大量重复计算

    解法二:

    记忆递归型

    class Solution {
    public:
        int sum_result[201][201];
        int minroad(int i, int j, vector<vector<int>> triangle){
            if (sum_result[i][j] != -1){
                return sum_result[i][j];
            }
            if (i == triangle.size() - 1){
                sum_result[i][j] = triangle[i][j];
            }
            else{
                int x = minroad(i + 1, j, triangle);
                int y = minroad(i + 1, j + 1, triangle);
                sum_result[i][j] = min(x, y) + triangle[i][j];
            }
            return sum_result[i][j];
    
    
        }
        int minimumTotal(vector<vector<int>>& triangle) {
            memset(sum_result, -1, sizeof(sum_result));
            int result = minroad(0, 0, triangle);
            return result;
    
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    能解出正确答案,leetcode还是超时JAVA版本不超时,不知道为啥

    解法三:动态规划
    自底向上 上山
    class Solution {
    public:
    
        int minimumTotal(vector<vector<int>>& triangle) {
            int n = triangle.size();
            vector<vector<int>> dp(n, vector<int>(n,0));
            for (int i = 0; i < n; i++) {
                dp[n-1][i] = triangle[n-1][i];
            }
            for (int i = triangle.size() - 2; i >= 0; --i) {
                for (int 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];
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    AC了,先初始化最底一层,DP[i][j]表示第i行第j列到底层的最短路径,最后dp[0][0]即为结果

    状态定义: f(i,j)=f(i,j) =f(i,j)= 从 (i,j)(i,j)(i,j) 到达最后一行的最小路径和。
    既然我们从下而上求解,那么我们就只能利用下面位置的值。

    转移方程:下一层两个能到达的位置的路径和的最小值,再加上当前位置的值,就是当前位置的最小路径和。
    f(i,j)  =  min  {  f(i+1,j),  f(i+1,j+1)  }  +  arr[i][j]f(i,j);=;min;{; f(i+1,j) ,; f(i+1,j+1) ; } ; + ; arr[i][j]
    f(i,j)=min{f(i+1,j),f(i+1,j+1)}+arr[i][j]
    这样做的优点是,每一个需要求解的点,都有两个下一个位置,普适性更高,且不用考虑最底层的点。

    初始值:最后一行的点都是初始值,不需要发生改变。
    f(row−1,j)=arr[row−1][j]f(row-1,j)=arr[row-1][j]
    f(row−1,j)=arr[row−1][j]

    返回值:顶位置 (0,0)(0,0)(0,0) 的最小路径和。
    return    f(0,0)return ;;f(0,0)
    returnf(0,0)

    上山空间优化

    方法一:一维数组
    class Solution {
    public:
    
        int minimumTotal(vector<vector<int>>& triangle) {
            int n = triangle.size();
            int dp[n];
    
            for (int i = 0; i < n; ++i) {
                dp[i] = triangle[n-1][i];
            }
            for (int i = n - 2; i >= 0; --i) {
                for (int j = 0; j < i + 1; ++j) {
                    dp[j] = min(dp[j],dp[j + 1]) + triangle[i][j];
                }
            }
            return dp[0];
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    使用一维数组存储结果

    方法二:不再额外申请空间,直接修改二维数组
    class Solution {
    public:
    
        int minimumTotal(vector<vector<int>>& triangle) {
            int n = triangle.size();
            for (int i = n - 2; i >= 0; --i) {
                for (int j = 0; j < i + 1; ++j) {
                    triangle[n-1][j] = min(triangle[n-1][j],triangle[n-1][j + 1]) + triangle[i][j];
                }
            }
            return triangle[n-1][0];
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    自顶向下 下山
    class Solution {
    public:
    
        int minimumTotal(vector<vector<int>>& triangle) {
            int n = triangle.size();
            vector<vector<int>> dp(n, vector<int>(n,0));
            dp[0][0] = triangle[0][0];
            for (int i = 1; i < n; ++i) {
                for (int j = 0; j <= i; ++j) {
                    if (j == 0){
                        dp[i][j] = dp[i-1][j] + triangle[i][j];
                    }else if (j == i){
                        dp[i][j] =dp[i-1][j-1] + triangle[i][j];
                    }else{
                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
                    }
                }
            }
            int minsum = dp[n-1][0];
            for (int j = 0; j < n; ++j) {
                minsum = min(minsum, dp[n-1][j]);
            }
            return minsum;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    状态定义:f(i,j)=f(i,j) =f(i,j)= 自顶 (0,0)(0,0)(0,0) 到当前位置 (i,j)(i,j)(i,j) 的最短路径和。
    每一步只能移动到下一行中相邻的结点上:
    (i−1,j−1)  或  (i−1,j)  →  (i,j)  →  (i+1,j)  或  (i+1,j+1)(i-1,j-1);或;(i-1,j); \to ;(i,j); \to ;(i+1,j);或;(i+1,j+1)
    (i−1,j−1)或(i−1,j)→(i,j)→(i+1,j)或(i+1,j+1)

    转移方程:上一行可到达当前位置的节点中的最小路径和,再加上当前位置的值,就是当前位置的最小路径和。
    f(i,j)=min  {  f(i−1,j−1)  ,    f(i−1,j)  }  +  arr[i][j]f(i,j) = min;{ ;f(i-1,j-1);,;; f(i-1,j); } ; +; arr[i][j]
    f(i,j)=min{f(i−1,j−1),f(i−1,j)}+arr[i][j]
    此外三角形的两个腰上的位置,都只有其上面的一个节点可以到达。

    f(i,0)=f(i−1,0)+arr[i][0]        f(i,i)=f(i−1,i−1)+arr[i][i]f(i,0)=f(i-1,0)+arr[i][0];;;;f(i,i)=f(i-1,i-1)+arr[i][i]
    f(i,0)=f(i−1,0)+arr[i][0]f(i,i)=f(i−1,i−1)+arr[i][i]

    初始值:顶位置 (0,0)(0,0)(0,0) 的最小路径和就是顶位置的值。
    f(0,0)=arr[0][0]f(0,0)=arr[0][0]
    f(0,0)=arr[0][0]

    返回值:最底层的数组的所有位置的路径和中的最小值。

  • 相关阅读:
    Spring-注解开发管理第三方Bean
    419-Linux基础(常用命令详解1)
    设计模式理论(一)软件设计原则
    1.2、Python基础-函数
    为什么建议将常量用const关键字来修饰
    HMI/SCADA软件架构和编程
    flinkdashboard未授权
    java MINio 操作工具类
    纺织企业如何选好网关实现数据采集和远程监控?
    pytorch学习------TensorBoard的使用
  • 原文地址:https://blog.csdn.net/BruceBorgia/article/details/133643570