【LeetCode】120. Triangle 基于C++和Java的分析及解法，动态规划

缺乏、安全感 2022-07-24 06:13 122阅读 0赞

120. Triangle

Total Accepted: 69567 Total Submissions: 229977 Difficulty: Medium

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
         [2],
        [3,4],
       [6,5,7],
      [4,1,8,3]
    ]

The minimum path sum from top to bottom is `11` (i.e., 2 + 3 + 5 + 1 = 11).

Note:  
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

【分析】

首先重述一下题意：输入一个（等腰）三角形数阵，寻找从三角形顶部达到底部的最小路径和，从顶部达到底部的过程中，从上一行的某个位置只能移动到下一行的与其相邻位置，如题中举例：第一行的2可以移动到第二行的3或者4；第二行的3只能移动到第三行的6或者5，第二行的4只能移动到第三行中的5或者7，以此类推。

此题明显是一个求取约束条件下最小路径的题，用动态规划（Dynamic Programming）解再合适不过，既然是DP问题，那么我们需要抽象出状态转移方程：把三角形数阵可以抽象成一个二维矩阵，那么：

设：从位置（i,j）达到底部的最小路径和为MP(i,j)；根据约束条件，从位置（i,j）只能达到下一行的（i+1,j）和（i+1,j+1）两个位置；如果，根据题意我们知道，位置（i,j）处的权值为输入三角形数阵对应的数据：triangle\[i\]\[j\];So,状态转移方程为：MP(i,j)=min\{MP(i+1,j),MP(i+1,j+1)\}+triangle\[i\]\[j\];三角形顶部到底部最小路径和：MP(0,0)=min\{MP(1,0),MP(1,1)\}+triangle\[0\]\[0\];而：MP(1,0)=min\{MP(2,0),MP(2,1)\}+triangle\[1\]\[0\];MP(1,1)=min\{MP(2,1),MP(2,2)\}+triangle\[1\]\[1\]....

很明显，这种自顶向下的求解方式会形成一个“树形结构”，并且自顶向下的求解过程，计算式中一直存在未知式，这显然不是一种好的方式，因此，我们采用自底向上的求解思路：以题目中给出的例子为例：

MP(3,0)=triangle\[3\]\[0\]=4;

MP(3,1)=triangle\[3\]\[1\]=1;

MP(3,2)=triangle\[3\]\[1\]=8;

MP(3,3)=triangle\[3\]\[1\]=3;

MP(2,0)=min\{MP(3,0),MP(3,1)\}+triangle\[2\]\[0\]=1+6=7;

MP(2,1)=min\{MP(3,1),MP(3,2)\}+triangle\[2\]\[1\]=1+5=6;

MP(2,2)=min\{MP(3,2),MP(3,3)\}+triangle\[2\]\[2\]=3+7=10;

MP(1,0)=min\{MP(2,0),MP(2,1)\}+triangle\[1\]\[0\]=6+3=9;

MP(1,1)=min\{MP(2,1),MP(2,2)\}+triangle\[1\]\[1\]=6+6=12;

MP(0,0)=min\{MP(1,0),MP(1,1)\}+triangle\[0\]\[0\]=9+2=11;

很明显，自底向上计算，最后MP(0,0)就是我们要的结果，采用两重循环即可完成求解,程序如下：

int minimumTotal(vector<vector<int>>& triangle) 
        {
            int length=triangle.size();
            if(length==0)return 0;
            if(length==1)return triangle[0][0];
            vector<int>temp(triangle.size(),0);   
            vector<vector<int>> MP(length,temp);
            MP[length-1]=triangle[length-1];//三角形底部一行任何一个位置达到底部最短路径为其本身
            
            for(int i=length-2;i>=0;i--)
            {
                for(int j=0;j<triangle[i].size();j++)
                {
                    MP[i][j]=min(MP[i+1][j],MP[i+1][j+1])+triangle[i][j];
                }
            }
            return MP[0][0];
        }

但是，像这样解决，需要消耗额外的空间，空间复杂度为O(n2)，因此该解法不可取，我们可以对其进行改进，借助输入数阵本身的空间来存储中间的迭代值：

完整代码为：

int minimumTotal(vector<vector<int>>& triangle) 
        {
            int length=triangle.size();
            if(length==0)return 0;
            if(length==1)return triangle[0][0];
            for(int i=triangle.size()-2;i>=0;i--)
            {
                for(int j=0;j<triangle[i].size();j++)
                {
                    triangle[i][j]=min(triangle[i+1][j],triangle[i+1][j+1])+triangle[i][j];
                }
            }
            return triangle[0][0];
        }

分析：这样做虽然表面上节省了空间消耗，但是事实上依赖于输入数阵的空间，空间消耗并没有实际减小，并且**会改变输入三角形数阵的原始数据**，很多时候，这样做都是不可取的。

**【解法一：基于C++解法】**

经过上面的分析，我们进一步优化空间消耗的问题，事实上，我们可以用一个一维数组来存储自底向上的路径向量，路径向量初始化为三角形数阵底部向量，此后每计算一次，更新一次，空间复杂度为O(n),且不影响输入三角形数阵的原始数据，程序如下：

int minimumTotal(vector<vector<int>>& triangle) 
        {
            int length=triangle.size();
            if(length==0)return 0;//特殊情况处理，容错机制
            if(length==1)return triangle[0][0];  
            vector<int> sum=triangle[triangle.size()-1];//初始化路径和存储向量，自底向上
            
            for(int i=triangle.size()-2;i>=0;i--)//自底向上迭代
            {
                for(int j=0;j<triangle[i].size();j++)
                {
                    sum[j]=min(triangle[i][j]+sum[j],triangle[i][j]+sum[j+1]);
                }
            }
            return sum[0];
        }

运行结果：

![Center][]

**【解法二：基于Java的解法】**

根据上面的思路，Java的解法程序如下：

public int minimumTotal(List<List<Integer>> triangle)
        {
            int length=triangle.size();
            if(length==0)return 0;
            if(length==1)return triangle.get(0).get(0);
            
            List<Integer> sum=triangle.get(length-1);
            for(int i=length-2;i>=0;i--)
            {
                for(int j=0;j<triangle.get(i).size();j++)
                {
                    int sum1=triangle.get(i).get(j)+sum.get(j);
                    int sum2=triangle.get(i).get(j)+sum.get(j+1);
                    sum.set(j,Math.min(sum1,sum2));
                }
            }
            return sum.get(0);
            
        }

[Center]: /images/20220722/21c16441170e49a5b3c6f8c4b0830d2c.png