https://leetcode-cn.com/problems/triangle/

Idea

Down-top思考
设三角形有n层 选择第n层第x个数 (1<=x<=n)
用F[n][x]表示选择第n层第x个数时候的最小路径和
由题意 可以得到状态转移方程
三角形最小路径和 - 图1

其中第n层第x个数的大小为num[n][x]
考虑边界条件 可以得到以下代码

Code

  1.     public static int minimumTotal(List<List<Integer>> triangle) {
  2.         int result=Integer.MAX_VALUE;
  3.         int[][] dp=new int[1000][1000];
  4.         dp[1][1]=triangle.get(0).get(0);
  5.         if(triangle.size()==1)
  6.             return dp[1][1];
  7.         dp[2][1]=triangle.get(1).get(0)+dp[1][1];
  8.         dp[2][2]=triangle.get(1).get(1)+dp[1][1];
  9.         if(triangle.size()==2)
  10.         {
  11.             if(dp[2][1]>dp[2][2])
  12.                 return dp[2][2];
  13.             else
  14.                 return dp[2][1];
  15.         }
  16.         int i;
  17.         for( i=2;i<triangle.size();i++)
  18.         {
  19.             for(int j=1;j<=i+1;j++)
  20.             {
  21.                 if(j-1==0) {
  22.                     dp[i + 1][j] = dp[i][j] + triangle.get(i).get(j - 1);
  23.                 }
  24.                 else if(i<j) {
  25.                     dp[i + 1][j] = dp[i][j - 1] + triangle.get(i).get(j - 1);
  26.                 }
  27.                 else if( dp[i][j-1]>dp[i][j] )
  28.                 {
  29.                     dp[i+1][j]=dp[i][j]+triangle.get(i).get(j-1);
  30.                 }
  31.                 else
  32.                 {
  33.                     dp[i+1][j]=dp[i][j-1]+triangle.get(i).get(j-1);
  34.                 }
  35.             }
  36.         }
  37.         for(int k=1;k<=i;k++)
  38.         {
  39.             if(result>dp[i][k])
  40.                 result=dp[i][k];
  41.         }
  43.         return result;
  44.     }

显然 这样做的时间复杂度为三角形最小路径和 - 图2,空间复杂度为三角形最小路径和 - 图3.

leetcode官方题解

观察状态方程 我们可以发现 对于要求的状态F[i][j],我们只需要存储他的上一步的状态f[i-1][…]就可以
因此 我们在进行动态规划循环的过程中 我们可以每次抛弃f[i-2]的状态 也就是 空间复杂度可以被优化为三角形最小路径和 - 图4

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] f = new int[2][n];
        f[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            int curr = i % 2;
            int prev = 1 - curr;
            f[curr][0] = f[prev][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; ++j) {
                f[curr][j] = Math.min(f[prev][j - 1], f[prev][j]) + triangle.get(i).get(j);
            }
            f[curr][i] = f[prev][i - 1] + triangle.get(i).get(i);
        }
        int minTotal = f[(n - 1) % 2][0];
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[(n - 1) % 2][i]);
        }
        return minTotal;
    }
}

终极优化
事实上,对于这样的一个三角形 我们只需要一个一维数组 来存储他们的 路径值就行了
遍历三角形
对于每一行
f[0]表示 第n行选0的最小值
f[1]表示 第n行选1的最小值
f[n]表示 第n行选n的最小值
[2],
[3,4],
[6,5,7],
[4,1,8,3]

首先 第n行选0 由于0只能来于第n-1行选0的值
可以写出f[0] += triangle.get(i).get(0);

同理 f[n] = f[n - 1] + triangle.get(n).get(n);

然后 我们首先计算最右边的 也就是第i行选i的数值
也就是 f[i] = f[i- 1] + triangle.get(i).get(i);

最后 我们再计算 f[i-1]….到 f[1]的值
如何计算f[i-1]?
我们知道f[i-1]的值 是由上一层的值 和第i层第i-1个数的大小 决定的

而这时候 我们只是把f[i]的值 变成了第i行选i的值

其他f[0] …. f[i-1]依然是 第i-1层的值
所以f[i-1] 的大小 由f[i-1] f[i-2] 和第i层第i-1个数的大小 决定
可以写出 f[i-1] = Math.min(f[i - 1], f[i-2]) + triangle.get(i).get(i-1);

同理 我们可以求出f[i-2] …..f[1]

f[0]的求法已经给出

于是可以得到下面的代码

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