首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【动态规划/路径问题】「最小路径和」问题的再变形 & 代入解题的注意点 ...

【动态规划/路径问题】「最小路径和」问题的再变形 & 代入解题的注意点 ...

作者头像
宫水三叶的刷题日记
发布2021-03-23 16:11:59
6340
发布2021-03-23 16:11:59
举报

前言

今天是我们讲解「动态规划专题」中的 路径问题 的第五天

我在文章结尾处列举了我所整理的关于 路径问题 的相关题目。

路径问题 我会按照编排好的顺序进行讲解(一天一道)。

你也先可以尝试做做,也欢迎你向我留言补充,你觉得与路径相关的 DP 类型题目 ~

题目描述

这是 LeetCode 上的「931. 下降路径最小和」,难度为 Medium

给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的「下降路径」「最小和」

下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。

在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。

具体来说,位置 (row,col) 的下一个元素应当是 (row+1,col-1)、(row+1,col) 或者 (row+1,col+1) 。

示例 1:

输入:matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出:13
解释:下面是两条和最小的下降路径,用加粗标注:
[[2,1,3],      [[2,1,3],
 [6,5,4],       [6,5,4],
 [7,8,9]]       [7,8,9]]

示例 2:

输入:matrix = [[-19,57],[-40,-5]]
输出:-59
解释:下面是一条和最小的下降路径,用加粗标注:
[[-19,57],
 [-40,-5]]

示例 3:

输入:matrix = [[-48]]
输出:-48

提示:

  • n == matrix.length
  • n == matrix[i].length
  • 1 <= n <= 100
  • -100 <= matrix[i][j] <= 100

动态规划(基于起点)

这题其实是 120.三角形最小路径和 的一道变形题。

120.三角形最小路径和 中,我们是从一个确定的起点出发,按照「某些条件」不断的进行转移,直到拿到一条「路径和最小」的路径。

本题则是能够从首行的任意位置开始转移。

我们可以定义一个 find() 函数,传入 矩阵首行的起点下标,返回 以首行该下标 为起点的 最小路径和

那么答案就是所有的 的最小值,i 的取值范围 [0,n)。代表能够从首行的任意下标出发。

而对于确定起点的「最小路径和」问题的求解,则是和我们昨天的 120.三角形最小路径和 分析方法完全一样。

由于我们需要先枚举起点,再进行 DP,这样做的复杂度是 的。

本题数据只有 ,因此计算量是 ,是可以过的。

PS. 如果你还不了解如何根据 复杂度/计算量 来判断是否超时的话,可以看看 这篇文章 的总结部分。

代码:

class Solution {
    int MAX = Integer.MAX_VALUE;
    public int minFallingPathSum(int[][] mat) {
        int n = mat.length;
        int ans = MAX;
        // 枚举首行的每个下标作为「起点」
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, find(mat, i));
        }
        return ans;
    }
    // 返回以 (0, u) 作为起点的最小路径和
    int find(int[][] mat, int u) {
        int n = mat.length;
        int[][] f = new int[n][n];
        for (int i = 0; i < n; i++) f[0][i] = i == u ? mat[0][i] : MAX;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                f[i][j] = MAX;
                int val = mat[i][j];
                if (f[i-1][j] != MAX) f[i][j] = Math.min(f[i][j], f[i-1][j] + val);
                if (j - 1 >= 0 && f[i-1][j-1] != MAX) f[i][j] = Math.min(f[i][j], f[i-1][j-1] + val);
                if (j + 1 < n  && f[i-1][j+1] != MAX) f[i][j] = Math.min(f[i][j], f[i-1][j+1] + val);
            }
        }
        int ans = MAX;
        for (int i = 0; i < n; i++) ans = Math.min(ans, f[n-1][i]);
        return ans;
    }
}
  • 时间复杂度:枚举首行起点复杂度为 ;对于一个确定的起点,找到其「最小路径和」的路径需要转移 个状态,复杂度为 。整体复杂度为 。
  • 空间复杂度:

动态规划(基于定义)

上述的解法,其实是基于我们 120.三角形最小路径和 的思路展开的。

而且算法的复杂度是 ,那么是否有更优的做法呢?

上述的解法总的来说分为两步:

  1. 枚举起点
  2. DP 求某个起点的最小路径和

DP 过程的复杂度我们是无法优化了,那么枚举起点的过程是否可以优化(省掉)呢?

答案是可以的。我们可以直接从 DP 定义出发,进行转移即可。

定义 为到达位置 的最小路径和。

那么最终答案为所有 的最小值,i 的取值范围为 [0,n)。代表最小路径的结尾可能是最后一行的任意位置。

代码:

class Solution {
    int MAX = Integer.MAX_VALUE;
    public int minFallingPathSum(int[][] mat) {
        int n = mat.length;
        int[][] f = new int[n][n];
        // 初始化:对于首行而言,每个位置的「最小成本」就是其「矩阵值」
        for (int i = 0; i < n; i++) f[0][i] = mat[0][i];
        // 从第二行开始,根据题目给定的条件进行转移
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int val = mat[i][j];
                f[i][j] = f[i - 1][j] + val;
                if (j - 1 >= 0) f[i][j] = Math.min(f[i][j], f[i-1][j-1] + val);
                if (j + 1 <  n) f[i][j] = Math.min(f[i][j], f[i-1][j+1] + val);
            }
        }
        int ans = MAX;
        for (int i = 0; i < n; i++) ans = Math.min(ans, f[n-1][i]);
        return ans;
    }
}
  • 时间复杂度:
  • 空间复杂度:

总结

如果考虑从「起点」出发,本题是在 120.三角形最小路径和 的基础上增加了一个「枚举起点」的考察点。

如果从「DP 状态定义」出发,那么这就是一题常规 DP 路径题。

有时候,我们会因为做过一些题目,很容易就代入已做过的题目的解法。

有时候这会让我们的思维很受限制,而且这样的解题方法往往会让算法复杂度会上升一个级别。

想想如果是在刚做完 120.三角形最小路径和 的情况下过来本题的话,大多数同学的第一想法会是去「枚举起点」,这是一个很人性的做法,在某个解决方案上堆逻辑。

使用做过的题目进行代入解题,其实本身没有问题。

但需要我们结合「复杂度/计算量」去分析是否超时。这点需要特别注意一下 ~

讲了好几天 DP 了,大家好好消化一下。周末愉快 ~

路径问题(目录)

62.不同路径(中等):路径问题第一讲

63.不同路径 II(中等):路径问题第二讲

64.最小路径和(中等):路径问题第三讲

120.三角形最小路径和(中等):路径问题第四讲

931.下降路径最小和(中等):本篇

1289.下降路径最小和 II(困难)

1575.统计所有可行路径(困难)

576.出界的路径数(中等)

1301.最大得分的路径数目(困难)

欢迎补充 ~

最后

这是我们「刷穿 LeetCode」系列文章的第 No.931 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2021-03-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 题目描述
  • 动态规划(基于起点)
  • 动态规划(基于定义)
  • 总结
  • 路径问题(目录)
  • 最后
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档