前言
作者：小蜗牛向前冲
专栏：小蜗牛算法之路
专栏介绍："蜗牛之道，攀登大厂高峰，让我们携手学习算法。在这个专栏中，将涵盖动态规划、贪心算法、回溯等高阶技巧，不定期为你奉上基础数据结构的精彩算法之旅。一同努力，追逐技术的星辰大海。"
一、什么是动态规划
1、什么是动态规划
2、动态规划的学习
二、动态规划刷题
1、第 N 个泰波那契数
a、解题思路：
b、代码
2、 面试题 08.01. 三步问题
a、解题思路：
b、代码
3 、746. 使用最小花费爬楼梯
a、解题思路
b、代码
4、解码方法
a、解题思路
b、代码
c、代码优化
5、不同路径（medium）
a、解题思路
b、代码
本期我们将探讨动态规划，并提供5道经典动态规划问题，难度由浅入深。
一、什么是动态规划
1、什么是动态规划
在学习算法的过程中，我们往往会遇到一些算法题是要用动态规划来解决。
但是做为小白的我们哪里知道动态规划是什么？
从概念上说
动态规划（Dynamic Programming）是一种解决复杂问题的算法设计技术。它通常用于解决具有重叠子问题和最优子结构性质的问题，通过将问题分解为更小的子问题，并利用子问题的解来构建原始问题的解。
看完概念我们知道什么是动态规划，求重叠类子问题的 一般会用到动态规划的思路。
那我们如何求学习动态规划
2、动态规划的学习
对于算法类题目，在我们掌握算法的基本原理后，就是进行大量刷题，进经验的总结。
求解动态规划的五步骤：
1、状态表示
在求解过程中，我们往往要创建dp表(其实就是数组），状态表示就是我们要找出dp表中值的含义是什么。
状态表 怎么来？
- 根据题目要求
- 经验+题目要求
- 分析题目的过程中，发现重复子问题
2、状态转移方程
简单说是和dp[i]有关的一个方程
3、初始化
保证在填写dp表的时候不越界
4、填写顺序
根据前面的计算得来，可以从前往后，也可以从后往前。
5、返回值
根据题目要求+状态表示
讲完了解题步骤，下面就进行刷题训练。
特别提醒：后面博客会带领大家由易到难进行刷题，每期都为五题。
二、动态规划刷题
1、第 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 2因为从 0----->1的走法我们已经考虑过了
走法为2
n=3时候
从0----->3或者说
我们让1----->3因为从 0----->1的走法我们已经考虑过了走法为1
也可以2----->3因为从 0----->2的走法我们已经考虑过了走法为2
走法为1+1+2=4
n=4时候
不管怎么说先走到1，在从1----->4走法为1
不管怎么说先走到2，在从2----->4走法为2
不管怎么说先走到3，在从3----->4走法为4
总共走法：1+2+4=7
大家这里是不是已经思路清晰起来了
1、转态表示
以i位置为结尾，正好是到达第N个台阶，所以我们认为：
dp[i]表示：到达i位置时，一共有多少方法。
2、状态转移方程
以i位置的状态，最近进的一步进行划分
从(i-1)--->i dp[i-1]种走法
从(i-2)--->i dp[i-2]种走法
从(i-3)--->i dp[i-3]种走法
所以状态方程为：dp[i]=dp[i-1]+dp[i-2]+dp[i-3] ;
3、初始化
这里我们注意我们用不到i==0,因为0台阶的研究没有意义。
dp[1] = 1, dp[2] = 2, dp[3] = 4;
4、 填表顺序
根据前面的推断肯定是从左往右。
5、返回值
根据题目要求和dp[i]就为dp[n]
b、代码
这题虽然和第一题非常相似但是有细节要处理、
class Solution { public: //取模 const int MOD = 1e9 + 7; int waysToStep(int n) { //处理边界情况： if (n == 1 || n == 2)return n; if (n == 3)return 4; //创建dp表 vector dp(n + 1); //初始化 dp[1] = 1, dp[2] = 2, dp[3] = 4; //填表 for (int i = 4; i 向下示例 3：
输入：m = 7, n = 3 输出：28
示例 4：
输入：m = 3, n = 3 输出：6
提示：
- 1
- 0 2因为从 0----->1的走法我们已经考虑过了
