动态规划问题 -- 斐波那契数列模型（解码方法)

动态规划问题分析五步曲

不清楚动态规划分析问题是哪关键的五步的少年们可以移步到
链接: 动态规划算法基础
这篇文章非常详细的介绍了动态规划算法是如何分析和解决问题的

题目概述

链接: 解码方法

1.状态表示（题目要求+自己的经验）
本题状态dp[i] ：dp[i]表示以i位置为结尾的子串有多少种编码方法

2.状态转移方程式推导
前提是要解码成功，如111 0就无法解码成功，11 10可以解码成功
综上所述，得出状态转移方程式
dp[i] = dp[i-1] + dp[i-2] (两种情况都可以解码成功)
dp[i] = 0 + dp[i-2] , dp[i] = dp[i-1] + 0(有一种情况解码不成功)
dp[i] = 0 两种方法均解码失败

3.初始化（防止越界，注意映射关系）
dp[i] = dp[i-1] + dp[i-2] (两种情况都可以解码成功)
当i < 2时就可能会出现数组越界的情况，为了方便后续dp的填表，我们多给dp表开一个头位置
对于dp的状态表示来说是一个无意义的位置，对于字符串S来说，代表的是空串
空串也是有一种解码方法的，那就是解码为空
因此初始化dp[0] = 1;
现在dp[1]表示的是S的第一个字符，即dp[1]表示的是s[0]
只要 1 <= s[0] <= 9 dp[1] = 0

4.填表顺序（分析要填i位置前一个依赖状态的位置）
本题的填表顺序显然是从左到右

5.返回值（状态表示+题目要求）
dp[dp.size()-1] 表示的就是以S的最后一个字符为结尾的解码总数

代码编写

有了动态规划五部曲的分析，咱们就可以写出非常优雅的代码了

 int numDecodings(string s) {int n = s.size();//极端情况，直接歇菜退出if(s[0] - '0' == 0) return 0;else if(n == 1) return 1;//未来dp要多开一个位置，导致dp的i下标对应的是s的i-1下标//我们给s增长一个无意义的位置，让dpi下标对应s的i下标string opt = "-";s = opt + s;vector<int> dp(n+1);dp[0] = 1,dp[1] = 1;  //初始化一下然后从i=2开始遍历for(int i = 2 ; i < dp.size() ; i++){int count = 0;int num = s[i] - '0';int prevnum = s[i-1] - '0';//本位置，自己解码，解码成功与解码失败count +=  num >= 1 && num <= 9 ? dp[i-1] : 0;//本位置，与前面一个位置联合解码，解码成功与解码失败count +=  prevnum != 0 &&   1 <= (prevnum*10 + num) &&   (prevnum*10 + num) <= 26 ? dp[i-2] : 0;dp[i] = count;}return dp[dp.size()-1];}

少年恭喜你又进步了一点点，继续加油吧