算法刷题系列上期：

• 递归、栈/队列、树、回溯、DP（8.29）
• 数组指针、前缀和/差分/树状数组、滑窗/单调队列/滚动哈希、二分（8.13）
• 链表题（8.29）

• 动态规划基础
  • 状态
  • 状态转移函数
• 题目
  • 三角形最小路径和

动态规划基础

状态

状态转移函数

题目

三角形最小路径和

时间：3ms 击败 77%

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle == null || triangle.isEmpty()) return 0;
        int n = triangle.size();
        int [][] f = new int [n][n];
        // ift0
        f[0][0] = triangle.get(0).get(0);
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                int lf = 0x3fffffff, rf = f[i - 1][j];
                if(j > 0) lf = f[i - 1][j - 1];
                // 最开始是 f[i][j] = lf < rf ? lf : rf; //
                f[i][j] = (lf < rf ? lf : rf) + triangle.get(i).get(j);
            } // f[i][j] = f[i - 1][j - 1]; 
            // 最开始忘记 triangle.get(i).get(j) 这部分了
            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int min = 0x3fffffff;
        for(int i = 0; i < n; i++){
            if(min > f[n - 1][i]){
                min = f[n - 1][i];
            }
        } return min;
    }
}