Offer必备算法11

���录

（）

动态规划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