动态规划应用——第三题三角矩阵

三角矩阵

动态规划——中等

三角形

给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，例如，给出的三角形如下：

[[20],[30,40],[60,50,70],[40,10,80,30]]

最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。

问题：从顶部到底部的最小路径和？

状态分析：

​ 子问题：从（0，0）到（i，j）的最小路径和

​ dp(i,j)：到(i,j)最小路径和

状态转移方程：

​ dp(i,j) = min( dp(i-1,j-1), dp(i-1,j) ) + array[i] [j];

​ 边界点只有唯一路径

​ ( j == 0 || j == i) : dp(i,j);

​ j == 0:dp(i-1,0) + array(i,j);

​ j == i: dp(i-1,j-1) + array(i,j);

初始值：(三角形的顶，只有一个)

​ dp(i,j) = 三角形的顶点

返回值：

​ min(dp( row-1,j ) );

dp二维数组 在原数组上 *** 作，也可自己定义个dp数组（空间复杂度为O(n)）

import java.util.*;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if(triangle.isEmpty())
            return 0;
        
        int row = triangle.size();
        int col = triangle.get(0).size();
        
        for(int i = 1;i<row;++i){
            for(int j = 0;j<=i;++j){
                int value = 0;
                if(j == 0){
                    value = triangle.get(i-1).get(0) + triangle.get(i).get(0);
                }else if(j == i)
                    value = triangle.get(i-1).get(i-1) + triangle.get(i).get(i);
                else{
                    value = Math.min(triangle.get(i-1).get(j-1),triangle.get(i-1).get(j)) + triangle.get(i).get(j);
                }
                triangle.get(i).set(j,value);
            }
        }
        //选出最后一行的最小值
        int min = triangle.get(row-1).get(0);
        for(int i = 0;i<row;i++){
            min = Math.min(min,triangle.get(row-1).get(i));
        }
        return min;
    }
}

解法二动态规划：自下向上

状态分析：

​ 子状态：从（n,n）,(n,n-1), … (1,0),(1,1)(0,0)到最后一行的最短路径和

​ dp(i,j): 从（i，j）到最后一行的最短路径和

状态递推：

​ dp（i，j) = min(dp(i+1,j),dp(i+1,j+1))+array(i,j);

初始值：

​ 底部一行的值不变；即：

​ dp(n,n) = triangle(n,n), … dp(n,0) = triangle(n,0);

返回值：

​ dp(0,0)

import java.util.*;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if(triangle.isEmpty())
            return 0;
        
        int row = triangle.size();
        int col = triangle.get(0).size();
        
        for(int i = row-2;i>=0;--i){
            for(int j = 0;j<=i;++j){
                int value = Math.min(triangle.get(i+1).get(j),triangle.get(i+1).get(j+1))+triangle.get(i).get(j);
                triangle.get(i).set(j,value);
            }
        }
        return triangle.get(0).get(0);
    }
}

动规一点也不难！！！？