JZTXT

算法刷题：DP专题（9.16，持续更）

发布时间 2023-09-16 20:24:52作者: 你好，一多

算法刷题系列上期：

目录

动态规划基础

状态

状态转移函数

题目

三角形最小路径和

时间：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;
    }
}