力扣AC：三角形最小路径和 - 动态规划

题目链接

三角形最小路径和

题目描述

实现代码

初次代码采用dfs的思想实现，每层元素只有两个选择：取或者不取，而从当前位置往下又有两个选择，取左边和去右边，因此，针对这两个选择进行dfs递归实现；

代码如下，结果超时：

package ccnu.agile.jdk8;
import ccnu.agile.utils.JSONUtils;
import java.util.ArrayList;
import java.util.List;
/**
 * @Description:
 * @Author: JreamY
 * @Date: 2022/2/25
 **/
public class Demo {
    int result = Integer.MAX_VALUE;
    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> list1=  new ArrayList<>();
        list1.add(2);
        List<Integer> list2 = new ArrayList<>();
        list2.add(3);
        list2.add(4);
        List<Integer> list3 = new ArrayList<>();
        list3.add(6);
        list3.add(5);
        list3.add(7);
        List<Integer> list4 = new ArrayList<>();
        list4.add(4);
        list4.add(1);
        list4.add(8);
        list4.add(3);
        triangle.add(list1);
        triangle.add(list2);
        triangle.add(list3);
        triangle.add(list4);
        System.out.println(new Demo().minimumTotal(triangle));
    }
    public int minimumTotal(List<List<Integer>> triangle) {
        dfs(triangle, 1, 0, triangle.get(0).get(0), triangle.size());
        return result;
    }
    public void dfs(List<List<Integer>> triangle, int layer, int curIdx, int res, int size) {
        if(layer == size+1) {
            return;
        }
        if(layer == size) {
            result = Math.min(result, res);
            return;
        }
        dfs(triangle, layer+1, curIdx, res+triangle.get(layer).get(curIdx), size);
        dfs(triangle, layer+1, curIdx+1, res+triangle.get(layer).get(curIdx+1), size);
    }
}

参考官方动态规划思想：记数组dp[i][j]表示从顶点出发到第i行j列位置的最短路径值，由三角形的特性可以知道：dp[i][j]的值只与dp[i-1][j]和dp[i-1][j-1]有关，其状态转移方程如下：

dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + c[i][j]

同时考虑边界条件：

1. dp[0][0] = c[0][0];
2. 对于j=0的数据，dp[i][j] = dp[i-1][j] + c[i][j];
3. 对于i == j的数据，dp[i][j] = dp[i-1][j-1] + c[i][j];

代码如下：

class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
//        dfs(triangle, 1, 0, triangle.get(0).get(0), triangle.size());
//        return result;
        int len = triangle.size();
        int[][] dp = new int[len][len];  // 顶部到第i行j列位置的最短路径和
        // 初始化边界条件
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i+1; j++) {
                if(j == 0) {
                    dp[i][j] = dp[i-1][j] + triangle.get(i).get(j);
                    continue;
                }
                if(i == j) {
                    dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);
                    continue;
                }
                dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j);
            }
        }
        int min = dp[len-1][0];
        for (int i = 1; i < len; i++) {
            if (dp[len-1][i] < min) {
                min = dp[len-1][i];
            }
        }
        return min;
    }
}