我爱学算法之——动态规划（一）
前言
动态规划简单来说：是一种把大问题拆成可复用的小问题的算法思想，通过记录子问题的解避免重复计算，用状态转移方程递推得到最终答案，本质是空间换时间，常用于求最优解和方案数。
利用动态规划去解决问题，最重要的是：
- 状态表示：明确 dp 数组中存的是什么（状态表示的是什么）
- 状态转移方程：找到当前答案和子问题答案的关系（如何计算）
一、第 N 个泰波那契数
题目解析
泰波那契序列：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给定一个整数n，返回第 n 个泰波那契数。
算法思路
对于这道题，状态表示和状态转移方程 在题目当中已经给出来了：
- 状态表示：
dp[i]表示第 i 个泰波那契数 - 状态转移方程：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
初始化：
在状态转移方程，求dp[i]时，用到了dp[i-1]、dp[i-2]、dp[i-3]，所以就要初始化dp[0]、dp[1]、dp[2]
代码实现
classSolution{public:inttribonacci(intn){vector<int>dp(n+3,0);dp[0]=0;dp[1]=dp[2]=1;for(inti=3;i<=n;i++)dp[i]=dp[i-1]+dp[i-2]+dp[i-3];returndp[n];}};对于这道题
0<= n <= 37，n是可以为 0的，这里多开辟了3个数据的空间；即使n 为 0，也不会出现访问越界的情况。
二、三步问题
题目解析
有个小孩要上楼梯，他可以一次上 1阶、2阶、3阶。
现在有 n 阶台阶的楼梯，求小孩有多少种上楼梯的方式。
示例：
n = 3，一共有4种走法：0-1-2-3、0-1-3、0-2-3、0-3
算法思路
状态表示：
对于这道题，要记录的就是：上到第 n 阶台阶，有多少走法
dp[i]表示：上到第 i 阶台阶，走法的数量
状态转移方程
要上到第 i 阶台阶，可以从第 i-1、i-2、i-3 阶上到第 i 阶；所以到第 i 阶台阶的走法 就等于 到第i-1、i-2、i-3阶台阶走法的总和。
即dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
初始化
在状态转移方程中，求 dp[i] 时用到了 dp[i-1]、dp[i-2]、dp[i-3]
这里就需要初始化：dp[1]、dp[2]、dp[3]（可以添加一个虚拟位置，这样初始化 dp[0]、dp[1]、dp[2]即可）
注意：
在计算的过程当中，数据可能超过 int 的范围，所以计算过程当中就对其 % 1000000007。
代码实现
classSolution{public:intwaysToStep(intn){inttmp=1000000007;vector<int>dp(n+3,0);dp[0]=dp[1]=1;dp[2]=2;for(inti=3;i<=n;i++)dp[i]=((dp[i-1]+dp[i-2])%tmp+dp[i-3])%tmp;returndp[n];}};三、使用最小花费爬楼梯
题目解析
给定一个数组 cost，其中 cost[i] 表示从 第 i 阶台阶向上爬需要支付的费用；一次可以向上爬一个或者两个台阶。
可以从下标为 0 或者 1 的台阶开始爬楼梯。
求 ： 爬到楼梯顶部的最低花费（注意：这里顶部指的是下标 n 位置）
算法思路
状态表示： dp[i] 表示爬到第 i 阶台阶的最低花费
状态表示：dp[i] = min(dp[i-1] + nums[i], dp[i-2] + nums[i-2]);
代码实现
classSolution{public:intminCostClimbingStairs(vector<int>&cost){intn=cost.size();vector<int>dp(n+2,0);for(inti=2;i<=n;i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}returndp[n];}};四、解码方法
题目解析
字母A-Z依次对应 数字1-25
给定一个只含数字的字符串，计算并返回 解法方法的总数。
示例：11106可以映射：AAJF（1,1,10,6）、KJF（11,10,6）；06不是一个合法的编码
算法思路
在确定状态表示时，可以根据题目描述和刷题经验来综合确定（例如：以 i 位置为结尾，…）
对于这道题，状态表示：dp[i] 表示 以 i 位置为结尾(区间[0,i])解码方法的总数
状态转移方程
状态转移方程，就思考 dp[i] 从何而来，如何去求
对于 i 位置，解码有两种情况：
- 如果
s[i] != '0'，s[i] 一个数字就可以进行解码 s[i-1]和s[i]组成数字进行解码
所以，当s[i] != '0'时：
- 如果
s[i-1]和s[i]组成的数字是合法编码，dp[i] = dp[i-1] + dp[i-2] - 如果
s[i-1]和s[i]组成的数字不是一个合法编码，dp[i] = dp[i-1]
当s[i] == '0'时
- 如果
s[i-1]和s[i]组成的数字是合法编码，dp[i] = dp[i-2] - 如果
s[i-1]和s[i]组成的数字不是一个合法编码，dp[i] = 0
初始化
在状态转移方程中，使用到了dp[i-1]和dp[i-2]，这里就需要初始化dp[0]、dp[1]
如果s[0] == '0'，dp[0] = 0；否则 dp[0] = 1
对于 dp[1]，初识为 0
- 如果
dp[0] != '0' && dp[1] != '0'，dp[1]++ - 如果
tmp >= 10 && tmp<=26，dp[1]++
代码实现
classSolution{public:intnumDecodings(string s){intn=s.size();vector<int>dp(n+2,0);dp[0]=s[0]!='0';if(n==1)returndp[0];if(s[0]!='0'&&s[1]!='0')dp[1]++;inttmp=(s[0]-'0')*10+(s[1]-'0');if(tmp>=10&&tmp<=26)dp[1]++;for(inti=2;i<n;i++){if(s[i]!='0')dp[i]+=dp[i-1];inttmp=(s[i-1]-'0')*10+(s[i]-'0');if(tmp>=10&&tmp<=26)dp[i]+=dp[i-2];}returndp[n-1];}};dp[i]+=dp[i-1];inttmp=(s[i-1]-'0')*10+(s[i]-'0');if(tmp>=10&&tmp<=26)dp[i]+=dp[i-2];}returndp[n-1];}};本篇文章到这里就结束了，感谢支持
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws