Offer必备算法11_斐波那契dp_四道力扣题详解（由易到难）

2024-03-07 03:04
文章标签 算法 dp 详解 必备 那契 offer 斐波 由易到难 四道 力扣题

本文主要是介绍Offer必备算法11_斐波那契dp_四道力扣题详解（由易到难），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

动态规划dp算法原理

①力扣1137. 第 N 个泰波那契数

解析代码1

解析代码2

②力扣面试题 08.01. 三步问题

解析代码

③力扣746. 使用最小花费爬楼梯

解析代码1

解析代码2

④力扣91. 解码方法

解析代码1

解析代码2

本篇完。

动态规划dp算法原理

        动态规划（Dynamic Programming）算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法

        动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

        与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上）。

（除此斐波那契dp外还有其它类型的dp在后面会更新。）

动态规划算法解决问题的分类：

计数

有多少种方式走到右下角 / 有多少种方法选出k个数使得和是sum

求最大值/最小值

从左上角走到右下角路径的最大数字和最长上升子序列长度

求存在性

取石子游戏,先手是否必胜 / 能不能取出k  个数字使得和是 sum

动态规划dp算法一般步骤：

  1. 确定状态表示（dp[ i ] 表示什么，一般以 i 位置为起点或结尾分析，化成子问题）
  2. 状态转移方程（斐波那契数列的状态转移方程为：dp[i] = dp[i-1] + dp[i-2]）
  3. 初始化（斐波那契数列初始化可以为dp[0] = 0, dp[1] = 1;）
  4. 填表顺序（斐波那契数列从左往右填）
  5. 返回值（如果斐波那契数列要求是第 n 个斐波那契数，返回dp[ n ] 即可）

①力扣1137. 第 N 个泰波那契数

1137. 第 N 个泰波那契数

 难度 简单

泰波那契序列 Tn 定义如下： 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537

提示：

  • 0 <= n <= 37
  • 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
class Solution {
public:int tribonacci(int n) {}
};

解析代码1

简单的DP，根据题目已经得到状态转移方程了：

class Solution {
public:int tribonacci(int n) {if(n <= 1) // 处理边界return n;vector<int> dp(n+1, 0);dp[1] = dp[2] = 1;for(int i = 3; i <= n; ++i){dp[i] = dp[i-1] + dp[i-2] + dp[i-3];}return dp[n];}
};

解析代码2

        滚动数组对解法1进行空间上的优化，后面类似的空间优化就不写了，因为笔试没用，面试能讲出来就行。

class Solution {
public:int tribonacci(int n) {if(n <= 1) // 处理边界return n;int a = 0, b = 1, c = 1, d = 1; // 滚动数组思想优化空间for(int i = 3; i <= n; ++i){d = a + b + c;a = b;b = c;c = d;}return d;}
};

②力扣面试题 08.01. 三步问题

面试题 08.01. 三步问题

难度 简单

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

 输入：n = 3 
 输出：4
 说明: 有四种走法

示例2:

 输入：n = 5
 输出：13

提示:

  1. n范围在[1, 1000000]之间
class Solution {
public:int waysToStep(int n) {}
};

解析代码

和上一题力扣1137. 第 N 个泰波那契数状态转移方程一样，就是要注意数据溢出。

class Solution {
public:int waysToStep(int n) {const int MOD = 1e9 + 7;if(n <= 2) // 处理边界return n;vector<int> dp(n+1, 1);dp[2] = 2;dp[3] = 4;for(int i = 4; i <= n; ++i){dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;}return dp[n];}
};

③力扣746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯

难度 简单

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {}
};

解析代码1

如果dp[ i ]表示到达i位置的最小花费，则到达dp[ i ] 就有以下两种情况：

  • 先到达dp[ i-1 ] 然后 支付cost[ i-1] 到达 dp[ i ]。
  • 先到达dp[ i-2 ] 然后 支付cost[ i-2] 到达 dp[ i ]。

题意及取两种情况小的那个，得到状态转移方程：dp[i] =min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n + 1, 0); // dp[i]表示到达i位置的最小花费for(int i = 2; i <= n; ++i){dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);}return dp[n]; // 楼顶是原数组最后位置的下一个}
};

解析代码2

如果dp[ i ]表示从 i 位置出发，到达楼顶，此时的最小花费，则dp[ i ] 就有以下两种情况：

  • 支付 cost[ i ]，往后走一步，从 i + 1的位置出发到终点
  • 支付 cost[ i ]，往后走两步，从 i + 2的位置出发到终点

则需要知道 i + 1 和 i + 2 位置的最小花费，及dp [i + 1] 和 dp[i + 2]。所以要从右往左填

则状态转移方程为：dp[i] = min(dp[i+1] + cost[i], dp[i+2] + cost[i]);

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n, 0); // dp[i]表示到达i位置的最小花费dp[n-1] = cost[n-1];dp[n-2] = cost[n-2];for(int i = n-3; i >= 0; --i){dp[i] = min(dp[i+1] + cost[i], dp[i+2] + cost[i]);}return min(dp[0], dp[1]);}
};

④力扣91. 解码方法

91. 解码方法

难度 中等

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

  • "AAJF" ，将消息分组为 (1 1 10 6)
  • "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。

提示：

  • 1 <= s.length <= 100
  • s 只包含数字，并且可能包含前导零。
class Solution {
public:int numDecodings(string s) {}
};

解析代码1

dp[i]表示字符串中区间，总编码方法

关于 i 位置的编码状况，可以分为下面两种情况：

  • 让 i 位置上的数单独解码成一个字母
  • 让 i 位置上的数与 i - 1 位置上的数结合，解码成一个字母

让 i 位置上的数单独解码成一个字母，就存在 解码成功 和 解码失败 两种情况：

  • 解码成功：dp[i] = dp[i - 1];（[0，i] 上所有解码结果后面填上一个字母即可） 
  • 解码失败：dp[i] = 0;（前面努力都白费）

让 i 位置上的数与 i - 1 位置上的数结合在⼀起，解码成一个字母，也存在 解码成功 和 解码失败 两种情况：

  • 解码成功：dp[i] = dp[i - 2];    原因同上。
  • 解码失败：dp[i] = 0;（前面努力都白费）
class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp(n, 0); // dp[i]表示字符串中[0，i]区间，总编码方法dp[0] = (s[0] != '0'); // 题目只有0-9，不等于0就能单独编码if(n == 1)return dp[0];if(s[0] != '0' && s[1] != '0') // 两个都能单独编码dp[1] += 1;int y = (s[0] -'0') * 10 + (s[1] - '0');if(y >= 10 && y <= 26) // 和在一起能编码，不含前导0dp[1] += 1;for(int i = 2; i < n; ++i){if(s[i] != '0') // 能单独编码dp[i] += dp[i-1];y = (s[i-1] -'0') * 10 + (s[i] - '0');if(y >= 10 && y <= 26) // 和在一起能编码，不含前导0dp[i] += dp[i-2];}return dp[n-1];}
};

解析代码2

解析代码1是直接初始化，有点麻烦，在其基础上可以添加辅助位置初始化，注意两个点：

  • 辅助结点里面的值要保证后续填表是正确的
  • 下标的映射关系（此题下标有的要减1）
class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp(n+1, 0); // 辅助结点简化dp[0] = 1;dp[1] = (s[0] != '0');for(int i = 2; i <= n; ++i){if(s[i-1] != '0') // 能单独编码dp[i] += dp[i-1];int y = (s[i-2] -'0') * 10 + (s[i-1] - '0');if(y >= 10 && y <= 26) // 和在一起能编码，不含前导0dp[i] += dp[i-2];}return dp[n];}
};

本篇完。

下一篇是链表的OJ，下下篇是动态规划的另一种类型：路径dp。

这篇关于Offer必备算法11_斐波那契dp_四道力扣题详解（由易到难）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/782210。

相关文章

Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu4826（三维DP）

hdu4826（三维DP）

这是一个百度之星的资格赛第四题 题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意：从左上角的点到右上角的点，每个点只能走一遍，走的方向有三个：向上，向下，向右，求最大值。 咋一看像搜索题，先暴搜，TLE,然后剪枝，还是TLE.然后我就改方法，用DP来做，这题和普通dp相比，多个个向上
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息，即可快速实现设备配网，是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递，利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力，实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后，即可发送相关配网数据。同时还支持与常规Sof
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
hdu4865(概率DP)

hdu4865(概率DP)

题意：已知前一天和今天的天气概率，某天的天气概率和叶子的潮湿程度的概率，n天叶子的湿度，求n天最有可能的天气情况。 思路：概率DP，dp[i][j]表示第i天天气为j的概率，状态转移如下：dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下： #include <stdio.h>#include
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2