【动态规划入门篇】只需三步解决它

作者：知心宝贝

2022 年 6 月 02 日
本文字数：2638 字
阅读完需：约 9 分钟

青蛙跳台阶

一、问题描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n （0 <= n <= 100）级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

二、题目要求

运行限制

最大运行时间：1s
最大运行内存: 128M

样例

输入：2  输出：2输入：7  输出：21输入：0  输出：1

复制代码

考察

1.动态规划入门2.建议用时5~15min

复制代码

三、问题分析

做动态规划需要几步，就像冰箱装大象一样，分成三步：

第一步：含义搞懂

通常动态规划都会用数组 dp[]存放东西，那存放在数组里面的究竟是什么？

这要看题目问我们什么，这一题就问青蛙跳台阶的方案数嘛，那么 dp[i]就代表第 i 个台阶有 dp[i]个方案，它问什么我们就存什么。

第二步：变量初始

dp[0]=1             题目样例给了dp[1]=1             1个台阶跨一步就到dp[2]=2             2个台阶可以跨1个台阶再跨1个，也可以一次性跨2个，所以两种方案dp[3]=3             3个台阶每次跨1个、先跨1个再跨2个、先跨2个再跨1个     ......

复制代码

初始变量一般找 2~5 个就行，下面才是重头戏啊！

第三步：关系归纳

搞清楚数组的含义和初始值之后，我们求的是第 n 个台阶方案数，题目又没给，怎么办？

找规律，做归纳总结，看看和前面的台阶方案有什么关系，这一步很重要，规律找不好直接芭比 q。

仔细看一下第二步的规律，后一个是不是等于前面两个相加，所以第 n 个公式为：

dp[n]=dp[n-1]+dp[n-2]。

三步走，打完收工！

四、编码实现

#include<iostream>using namespace std;int numWays(int n){    if(n<=1) return 1;    int dp[n+1],i;    dp[0]=1,dp[1]=1;//初始化变量    for(i=2;i<=n;i++)    {      //规律        dp[i]=(dp[i-1]+dp[i-2])%1000000007;//取模别忘了    }    return dp[n];//返回结果}int main(){  int k;  cin>>k;//输入台阶数目  cout<<numWays(k);//赋值给动态规划功能的函数  return 0;}

复制代码

五、测试结果

六、总结与提高

如果题目改成：

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶......一直到 n 级台阶。求该青蛙跳上一个 n （0 <= n <= 100）级的台阶总共有多少种跳法，做完之后可以在评论区交流结果。

机器人走迷宫

一、问题描述

一个机器人位于一个 m x n **网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

题目链接：机器人走迷宫

二、题目要求

考察

1.动态规划中等题型2.建议用时5~15min

复制代码

数据要求

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

样例

m=3，n=7     输出28m=3，n=2     输出3m=3，n=3     输出6

复制代码

三、问题分析

这也是一道比较典型的动态规划问题，动态规划没做过的可以看这一篇入门：

算法题每日一练---第34天：青蛙跳台阶

还是用我们的三步走老套路：

第一步含义搞懂：

这是二维数组，要求出不同路径，那么就用二维数组 dp[i][j]存储不同的路径个数。

第二步变量初始：

dp[1][1]=1 原地踏步不就是吗？一步步写太多了，不想写了，我放一个编译结果图片，偷懒一下。

复制代码

周围一圈都是初始化 0

第三步规律归纳：

看看上面的图片有什么特别的地方，有时间可以自己动手写一下，印象会更加深刻，当时我就写了一遍。

是不是当前数组位置的到数 = 左面的数字 + 上面的数字啊！

所以 dp[m][n]=dp[m][n-1]+dp[m-1][n];

三步走，打完收工！

四、编码实现

#include<iostream>using namespace std;int uniquePaths(int m, int n) {    int i,j,dp[102][102]={0};//初始化变量    for(i=1;i<=m;i++)//循环判断    {        for(j=1;j<=n;j++)        {            if(i==1&&j==1)                {                    dp[1][1]=1;//初始化变量                }            else                dp[i][j]=dp[i][j-1]+dp[i-1][j];//规律归纳        }    }//    for(i=0;i<=m;i++)//输出当前数组元素的值//    {//        for(j=0;j<=n;j++)//        {//            cout<<dp[i][j]<<"      ";//        }cout<<"\n";//    }    return dp[m][n];//返回结果}int main(){  int m,n;  cin>>m>>n;//输入数组大小  cout<<uniquePaths(m, n) ;//赋值给动态规划功能的函数  return 0;}

复制代码

五、测试结果

输入 3 7：

连续子数组的最大和

一、问题描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

题目链接：连续子数组的最大和

二、题目要求

要求：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
要求时间复杂度为 O(n)。

示例:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

复制代码

考察

1.动态规划中等题型2.建议用时5~15min

复制代码

三、问题分析

这也是一道比较典型的动态规划问题，动态规划没做过的可以看这一篇入门题解：

算法题每日一练---第34天：青蛙跳台阶

还是用我们的三步走老套路：

第一步含义搞懂：

这一题在力扣上面是简单题，但我第一次做想了半天要怎么往动态规划上面靠拢，瞬间觉得这一题不简单。

先看题目要求是什么，求出数组中连续子数组的最大值，下面就以示例里面的值讲解。

设一维数组 dp[i]就代表从区间 1~i 的范围里面，以 num[i]结尾的连续子数组最大值。

第二步变量初始：

这一题我们只需要初始一个变量就行，那就是 dp[0]=nums[0]

第三步规律归纳：

这一步就是最关键的一步了，能不能娶上媳妇就看最后一哆嗦了。

我先把 nums 数组和 dp 数组里面的值列举一下，看看能不能发现规律：

仔细看一下，每一个 dp[i]是如何得到的，是不是当前位的 num[i]加上前面一个 dp[i-1]数又或是没加，那没加是因为前面的数是负的嘛。所以，规律出现：

三步走，打完收工！

四、编码实现

#include<iostream>using namespace std;int main(){    long long int i,n,dp[100005],nums[100005],max;//初始化变量    cin>>n;//输入数组大小    for(i=0;i<n;i++)    {      cin>>nums[i];//输入数组数据  }    max=dp[0]=nums[0];//变量初始    for(i=1;i<n;i++)//循环判断    {        if(dp[i-1]<=0)//负数是本身        {            dp[i]=nums[i];        }        else            dp[i]=nums[i]+dp[i-1];//正数加上上一个        if(dp[i]>max)//是否大于当前max        {            max=dp[i];        }    }    cout<<max;//输出结果  return 0;}

复制代码

五、测试结果

发布于: 刚刚阅读数: 5

知心宝贝

关注

公众号：穿越计算机的迷雾 2022.03.07 加入

生于尘埃溺于人海死于理想高台

发布

暂无评论

创作场景

【动态规划入门篇】只需三步解决它

青蛙跳台阶

一、问题描述

二、题目要求

运行限制

样例

考察

三、问题分析

第一步：含义搞懂

第二步：变量初始

第三步：关系归纳

四、编码实现

五、测试结果

六、总结与提高

机器人走迷宫

一、问题描述

二、题目要求

考察

数据要求

样例

三、问题分析

第一步含义搞懂：

第二步变量初始：

第三步规律归纳：

四、编码实现

五、测试结果

连续子数组的最大和

一、问题描述

二、题目要求

考察

三、问题分析

第一步含义搞懂：

第二步变量初始：

第三步规律归纳：

四、编码实现

五、测试结果

知心宝贝

评论