leetcode 120. Triangle 杨辉三角形3 + BFS广度优先遍历

喜欢ヅ旅行 2022-06-08 04:17 143阅读 0赞

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.

我这里是遍历求解，做一个简单的BFS广度优先遍历。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    public class Solution 
    {
        public int minimumTotal(List<List<Integer>> tri) 
        {
            List<List<Integer>> res=new ArrayList<>();
            if(tri==null || tri.size()<=0)
                return 0;
    
            if(tri.size()==1)
                return tri.get(0).get(0);
    
            //本质上就是迭代求解
            for(int i=1;i<tri.size();i++)
            {
                List<Integer> pre=tri.get(i-1);
                List<Integer> one=tri.get(i);
                for(int j=0;j<one.size();j++)
                {
                    if(j==0)
                        one.set(j, one.get(0)+pre.get(0));
                    else if(j==pre.size())
                        one.set(j, one.get(j)+pre.get(pre.size()-1));
                    else
                    {
                        int min=Math.min(one.get(j)+pre.get(j),one.get(j)+pre.get(j-1));
                        one.set(j, min);
                    }
                }
            }
    
            List<Integer> last=tri.get(tri.size()-1);
            int min=Integer.MAX_VALUE;
            for(int i=0;i<last.size();i++)
            {
                if(last.get(i)< min)
                    min=last.get(i);
            }
            return min;
        }
    }

下面是C++的做法，就是一个很简单的DP动态规划问题，也就是可以看成一个BFS广度优先遍历问题的解决

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <climits>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int minimumTotal(vector<vector<int>>& t)
        {
            if (t.size() <= 0)
                return 0;
            for (int i = 1; i < t.size(); i++)
            {
                for (int j = 0; j < t[i].size(); j++)
                {
                    if (j == 0)
                        t[i][0] += t[i - 1][0];
                    else if (j == t[i - 1].size())
                        t[i][t[i - 1].size()] += t[i - 1][t[i - 1].size() - 1];
                    else
                        t[i][j] += min(t[i - 1][j], t[i - 1][j - 1]);
                }
            }
    
            int minSum = numeric_limits<int>::max();
            for (int i = 0; i < t[t.size() - 1].size(); i++)
                minSum = min(minSum, t[t.size() - 1][i]);
            return minSum;
        }
    };