LeetCode 120. 三角形最小路径和120. 三角形最小路径和参考资料

104 阅读 0 评论 69 点赞

我是靠谱客的博主喜悦发夹，最近开发中收集的这篇文章主要介绍LeetCode 120. 三角形最小路径和120. 三角形最小路径和参考资料，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

120. 三角形最小路径和

题目描述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
在这里插入图片描述
进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

解题思路

若定义 f(i, j) 为 (i, j) 点到底边的最小路径和，则易知递归求解式为:

f(i, j) = min(f(i + 1, j), f(i + 1, j + 1)) + triangle[i][j]

由此，我们将任一点到底边的最小路径和，转化成了与该点相邻两点到底边的最小路径和中的较小值，再加上该点本身的值。

思路一：递归

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    const dfs = function (i, j) {
        if (i == triangle.length) {
            return 0;
        }
        return Math.min(dfs(i + 1, j), dfs(i + 1, j + 1)) + triangle[i][j];
    }
    return dfs(0, 0);
};

暴力搜索会有大量的重复计算，导致 超出时间限制.

优化版本
利用二维数组进行记忆化

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    let len = triangle.length,
        memo = Array.from(Array(len), () => Array(len))
    const dfs = function (i, j) {
        if (i == len) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        return memo[i][j] = Math.min(dfs(i + 1, j), dfs(i + 1, j + 1)) + triangle[i][j]; 
    }
    return dfs(0, 0);
};

时间复杂度：O( $n^2$ ) ，n 为三角形的行数。
空间复杂度：O( $n^2$ ) ;

思路二：动态规划

定义二维 dp 数组，将解法一中「自顶向下的递归」改为「自底向上的递推」。

1. 状态定义：
dp[i][j] 表示从点 (i, j) 到底边的最小路径和。

2、状态转移：
dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]

3. 初始状态
一开始都初始化为0

4. 返回值
返回 dp[0][0]

实现代码如下：

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    let len = triangle.length,
        // dp[i][j] 表示从点 (i, j) 到底边的最小路径和
        dp = Array.from(Array(len + 1), () => Array(len + 1).fill(0));

    // 从三角形的最后一行开始递推
    for (let i = len - 1; i >= 0; i--) {
        for (let j = 0; j <= i; j++) {
            dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
        }
    }
    return dp[0][0];
};

时间复杂度：O( $n^2$ ) ，n 为三角形的行数。
空间复杂度：O( $n^2$ ) ;

空间复杂度优化
在实际递推中我们发现，计算 dp[i][j] 时，只用到了下一行的 dp[i + 1][j] 和 dp[i + 1][j + 1] ，因此 dp数组定义成一维数组就行，这样可以将将 O( $n^2$ ) 的空间复杂度优化成 O(n)
优化后代码如下：

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    let len = triangle.length;
    if (len == 1) {
        return triangle[0][0]
    } 
    let dp = Array(len + 1).fill(0);

    // 从三角形的最后一行开始递推
    for (let i = len - 1; i >= 0; i--) {
        for (let j = 0; j <= i; j++) {
            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];
        }
    }
    return dp[0];
};