day-30 三角形最小路径和

思路
典型的动态规划问题,状态方程可以理解为min[i][j]=min[i][j]+Math.min(min[i-1][j-1],min[i-1][j])，在考虑边界的特殊处理即可

解题方法
最后得到的最后一行中的最小值即为最小路径和

Code

class Solution {

    public int minimumTotal(List<List<Integer>> triangle) {

        int n=triangle.size();
        for(int i=1;i<n;i++){

            int m=triangle.get(i).size();
            for(int j=0;j<m;j++){

                if(j==0){

                    triangle.get(i).set(j,triangle.get(i-1).get(j)+triangle.get(i).get(j));
                }else if(j==m-1){

                    triangle.get(i).set(j,triangle.get(i-1).get(j-1)+triangle.get(i).get(j));
                }else{

                    triangle.get(i).set(j,triangle.get(i).get(j)+
                    Math.min(triangle.get(i-1).get(j),triangle.get(i-1).get(j-1)));
                }
            }

        }
        int ans=99999;
        for(int i=0;i<triangle.get(n-1).size();i++){

            if(triangle.get(n-1).get(i)<ans)
            ans=triangle.get(n-1).get(i);
        }
        return ans;
    }
}

原文链接: https://blog.csdn.net/qq_53568730/article/details/138525524