【动态规划专栏】专题二:路径问题--------4.下降路径最小和

简介: 【动态规划专栏】专题二:路径问题--------4.下降路径最小和


题目来源

本题来源为:

Leetcode 931. 下降路径最小和

题目描述

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

下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

题目解析

题目很好理解,注意一点就是选择下一行发的元素是离他最近的三个位置的元素。

算法原理

1.状态表示

经验+题目要求

对于本题而言就是:

dp[i][j]表示:走到[i,j]位置的时候,最小的下降路径

2.状态转移方程

分三种情况:

因此状态方程为:

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

3.初始化

本次的初始化需要加两列一行。

4.填表顺序

整体从上往下

5.返回值

返回最后一行的最小值

代码实现

动态规划的代码基本就是固定的四步:

1.创建dp表
2.初始化
3.填表
4.返回值

本题完整代码实现:

class Solution 
{
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        int n=matrix.size();
        //创建dp表
        vector<vector<int>> dp(n+1,vector<int>(n+2,INT_MAX));
        //初始化第一行
        for(int i=0;i<n+2;i++)
          dp[0][i]=0;
        
        //填表
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                //抄状态转移方程
                dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]))
                        +matrix[i-1][j-1];
            }
        }
        int ret=INT_MAX;
        for(int j=1;j<=n;j++)
        {
            
            ret=min(ret,dp[n][j]);
        }
        return ret;
    }
};

时间复杂度:O(N)

空间复杂度:O(N)

相关文章
|
算法
【学会动态规划】下降路径最小和(8)
【学会动态规划】下降路径最小和(8)
39 0
|
5月前
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
6月前
|
算法 机器人
【动态规划专栏】专题二:路径问题--------2.不同路径II
【动态规划专栏】专题二:路径问题--------2.不同路径II
44 0
|
6月前
|
机器学习/深度学习
动态规划|【路径问题】|931.下降路径最小和
动态规划|【路径问题】|931.下降路径最小和
|
机器学习/深度学习 Cloud Native
【刷题日记】931. 下降路径最小和
本次刷题日记的第 71 篇,力扣题为:931. 下降路径最小和 ,中等
|
6月前
|
算法 测试技术 C++
【动态规划】【map】【C++算法】1289. 下降路径最小和 II
【动态规划】【map】【C++算法】1289. 下降路径最小和 II
|
6月前
LeetCode题:931下降路径最小和
LeetCode题:931下降路径最小和
45 0
|
6月前
|
算法 前端开发
前端算法-路径总和
前端算法-路径总和
|
6月前
|
算法
算法编程(七):路径总和
算法编程(七):路径总和
44 0
图解LeetCode——437. 路径总和 III
图解LeetCode——437. 路径总和 III
82 1
图解LeetCode——437. 路径总和 III