一、动态规划的算法原理
这是本人动态规划的第一篇文章，所以先阐述一下动态规划的算法原理以及做题步骤。动态规划本人的理解就是通过题目所给的条件正确地填满dp表（一段数组）。首先要先确定好dp表每个位置的值所代表的含义是什么，然后通过题目条件以及经验推出状态转移方程，第三个就是初始化，确定填表顺序以及保证填表不越界，最后输出题目所需的结果，大致就是这个思路。
二、斐波那契数列模型例题分析
1137. 第 N 个泰波那契数 - 力扣（LeetCode）
本题的思路较为简单，状态转移方程已经给出，直接上代码：
class Solution { public: int tribonacci(int n) { vector<int> v1(n+1); //初始化 if(n == 1) return 1; else if(n == 2) return 1; else if(n == 0) return 0; v1[0] = 0; v1[1] = 1; v1[2] = 1; for(int i = 3; i <= n; i++) { v1[i] = v1[i-1] + v1[i-2] + v1[i-3]; } return v1[n]; } };
面试题 08.01. 三步问题 - 力扣（LeetCode）
解析：
假设小孩此时正处于某一台阶上，那他是如何到达这一台阶的呢？是不是他有可能是从该台阶的前一个台阶跳上来的，也可能是从该台阶的前两个台阶跳上来的，也可能是从该台阶的前三个台阶跳上来的，所以小孩到某一台阶就有三种可能情况，也即dp表中某个位置的值就是这个位置前三个位置的值相加，从而确定出了状态转移方程。
class Solution { public: int waysToStep(int n) { //创建dp表 vector<int> v1(n+1); if(n ==1) return 1; if(n == 2) return 2; if(n == 3) return 4; //初始化 v1[1] = 1;v1[2] = 2; v1[3] = 4; for(int i = 4; i <= n; i++) { //确定状态转移方程，这里需要注意，加数的和可能会越界，根据题目要求要对1000000007取模 v1[i] = ((v1[i-1] + v1[i-2]) % 1000000007 + v1[i-3])%1000000007; } return v1[n]; } };
解析：
要确定每一级楼梯最低花费，通过比较前两级楼梯，确定应该加的值，从而确定状态转移方程。
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int length = cost.size(); //dp表 vector<int> MinCost(length); //初始化 for(int i = 0; i<cost.size(); i++) { MinCost[i] = cost[i]; } //状态转移方程 for(int i = 2; i<length; i++) { if(MinCost[i-1] < MinCost[i-2]) { MinCost[i] += MinCost[i-1]; } else { MinCost[i] += MinCost[i-2]; } } if(MinCost[cost.size() - 1] < MinCost[cost.size() - 2]) { return MinCost[cost.size() - 1]; } else { return MinCost[cost.size() - 2]; } } };
解析：
选定一个位置作为结尾，如果这个位置的值不为零，就看其能否与前一个位置的值组成合法编码，如果能，这个位置的值就是它的前一个位置加上它的前前一个位置的值，如果不能，这个位置的值就是它的前一个位置的值；如果这个位置的值为零，就看其能否与前一个位置的值组成合法编码，如果能，这个位置的值就是它的前前一个位置的值。
class Solution { public: int numDecodings(string s) { int len = s.length(); int arr[len]; const char* str; str = s.c_str(); for(int i = 0; i<len; i++) { arr[i] = str[i] - 48; } //处理特殊情况 if(arr[0] == 0) { return 0; } else if(len == 1 && arr[0] != 0) { return 1; } for(int i = 1; i<len; i++) { //例：30 if(arr[i] == 0 && (arr[i-1] >2)) { return 0; } //例：1001 else if(i+1 < len && arr[i] == 0 && arr[i+1] == 0) { return 0; } } for(int i = 0; i<len; i++) { cout << arr[i] << " "; } //dp表 vector<int> vect(len+1); //初始化 vect[0] = 1;vect[1] = 1; //状态转移方程 for(int i = 2; i < vect.size(); i++) { if(arr[i-1] != 0) { if(arr[i-2] != 0 && ((arr[i-1] + arr[i-2]*10) <= 26)) { vect[i] = vect[i-1] + vect[i-2]; } else { vect[i] = vect[i-1]; } } else { vect[i] = vect[i-2]; } } return vect[len]; } };
