题解 | #三角形最小路径和#

总结：
使用动态规划解决，空间复杂度可以优化，从n^2,2n,n。参考如下：
https://leetcode.cn/problems/triangle/solution/san-jiao-xing-zui-xiao-lu-jing-he-by-leetcode-solu/

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param triangle int整型二维数组 
     * @return int整型
     */
    public int minTrace (int[][] triangle) {
        // write code here
        //方法一使用空间n^2
//         int n = triangle.length;
//         int[][] dp = new int[n][n];
//         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][j-1]+triangle[i][j];
//                 else
//                     dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j];
//             }
//         }
//         int min = dp[n-1][0];
//         for(int i=1;i<n;i++)
//             min = Math.min(min,dp[n-1][i]);
//         return min;
        //方法二 空间复杂度2n
//         int n = triangle.length;
//         int[][] f = new int[2][n];
//         f[0][0] = triangle[0][0];
//         int index = 0;
//         for(int i=1;i<n;i++)
//             for(int j=0;j<=i;j++){
//                 if((i&1)==1)
//                     index = 1;
//                 else
//                     index = 0;
//                 if(j==0)
//                     f[index][j] = f[1-index][j]+triangle[i][j];
//                 else if(j==i)
//                     f[index][j] = f[1-index][j-1]+triangle[i][j];
//                 else
//                     f[index][j] = Math.min(f[1-index][j],f[1-index][j-1])+triangle[i][j];

//             }
//         if(((n-1)&1)==0)
//             index = 0;
//         else 
//             index = 1;
//         int min = f[index][0];
//         for(int i=1;i<n;i++)
//             min = Math.min(min,f[index][i]);
//         return min;
        //方法三 空间复杂度n
        int n = triangle.length;
        int[] f= new int[n];
        f[0] = triangle[0][0];
        for(int i=1;i<n;i++)
            for(int j=i;j>=0;j--){
                if(j==0)
                    f[j] = f[j]+triangle[i][j];
                else if(j==i)
                    f[j] = f[j-1]+triangle[i][j];
                else
                    f[j] = Math.min(f[j],f[j-1])+triangle[i][j];
            }
        int min = f[0];
        for(int i=1;i<n;i++){
            min = Math.min(min,f[i]);
        }
        return min;

    }
}