DP sword finger offer II 100. sum of minimum paths in triangle

Catalog

solution 1 Dynamic programming of two-dimensional array  

  solution 2  Dynamic planning of optimized space

---

solution 1 Dynamic programming of two-dimensional array  

package LeetCode.DP;

import java.util.List;

public class OfferII100 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int length=triangle.size();
        int dp[][]= new int [length][length];
        //dp[m][n] From 0 0  To m n The shortest distance is dp[m][n]
        dp[0][0]=triangle.get(0).get(0);
        for (int i = 1; i <length; i++) {
                dp[i][0]=dp[i-1][0]+triangle.get(i).get(0);// about d[[i][0] Boundary treatment of 
            for (int j = 1; j <i; j++) {
                dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j-1])+triangle.get(i).get(j);
            }
                dp[i][i]=dp[i-1][i-1]+triangle.get(i).get(i);// about dp[i][i] Boundary treatment of 
        }
        int min=dp[length-1][0];
        for (int i = 0; i < length; i++) {
            if(min>dp[length-1][i]){
                min=dp[length-1][i];
            }
        }
        return min;
    }



}

  solution 2  Dynamic planning of optimized space

 

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

}