2025.9.29学习日记

public int minScoreTriangulation(int[] values) {
    //原问题可以转换成更小的子问题 贪心的拆分为最小
    int n = values.length;
    int[][] memo = new int[n][n];
    for(int[] row:memo){
        Arrays.fill(row,-1);
    }
    return dfs(0, n-1, values, memo);
}
private int dfs(int i , int j , int[] v, int[][] memo){
    if(i + 1 == j){
        return 0;
    }
    if(memo[i][j] != -1){
        return memo[i][j];
    }
    int res = Integer.MAX_VALUE;
    for(int k = i + 1 ; k < j ; ++k){
        int subRes = dfs(i,k,v,memo) + dfs(k,j,v,memo) + v[i] * v[j] * v[k] ;
        res = Math.min(subRes,res);
    }
    return memo[i][j] = res;
}

public int minScoreTriangulation(int[] v) {
    //原问题可以转换成更小的子问题 贪心的拆分为最小
    int n = v.length;
    int[][] f = new int[n][n];
    for(int i = n - 3 ; i >= 0 ; --i){
        for(int j = i + 2 ; j < n ; ++j){
            f[i][j] = Integer.MAX_VALUE;
            for(int k = i + 1 ; k < j ; ++k){
                f[i][j] = Math.min(f[i][j] , f[i][k] + f[k][j] + v[i] * v[j] * v[k]);
            }
        }
    }
    return f[0][n-1];
}