Offer必备算法11

03-10 7238阅读 0评论

（图片来源网络，侵删）

动态规划dp算法原理

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

解析代码1

解析代码2

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

（图片来源网络，侵删）

解析代码

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

解析代码1

解析代码2

④力扣91. 解码方法

解析代码1

解析代码2

本篇完。

动态规划dp算法原理

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

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

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

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

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

计数	有多少种方式走到右下角 / 有多少种方法选出k个数使得和是sum
求最大值/最小值	从左上角走到右下角路径的最大数字和最长上升子序列长度
求存在性	取石子游戏,先手是否必胜 / 能不能取出k 个数字使得和是 sum

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

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

提示：

相关阅读：

1、Axios使用

2、【NodeMcu-ESP8266】引脚使用参考指南——推荐收藏

3、基于单片机STM32的智能衣柜设计（可以写进毕设与简历的项目）

4、【数据结构】图论（图的储存方式，图的遍历算法DFS和BFS、图的遍历算法的应用、图的连通性问题）

5、使用FastDDS编译IDL文件

免责声明

1、本网站属于个人的非赢利性网站，转载的文章遵循原作者的版权声明。
2、本网站转载文章仅为传播更多信息之目的，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所
提供信息的准确性及可靠性，但不保证信息的正确性和完整性，且不对因信息的不正确或遗漏导致的任何
损失或损害承担责任。
3、任何透过本网站网页而链接及得到的资讯、产品及服务，本网站概不负责，亦不负任何法律责任。
4、本网站所刊发、转载的文章，其版权均归原作者所有，如其他媒体、网站或个人从本网下载使用，请在
转载有关文章时务必尊重该文章的著作权，保留本网注明的“稿件来源”，并白负版权等法律责任。

手机扫描二维码访问