动态规划的基本思想是利用之前已经计算过的结果，通过递推关系式来计算当前问题的解。

整体思路

• 状态表示
• 状态转移方程
• 初始化
• 填表顺序
• 返回值

---

第 N 个泰波那契数

题目： 第 N 个泰波那契数

思路

• 状态表示：根据题目要求，dp[i]表示第i个泰波那契数列
• 状态转移方程：题目已经给出，dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
• 初始化：将前三个数初始化，防止越界
• 填表顺序：从左往右
• 返回值：dp[n]

C++代码

class Solution
{
public:int tribonacci(int n){// 特判边界if (n == 0) return 0;if (n == 1) return 1;if (n == 2) return 1;vector<int> dp(n + 1);dp[0] = 0;dp[1] = dp[2] = 1;for (int i = 3; i <= n; ++i){dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];}return dp[n];}
};

三步问题

题目：三步问题

思路

• 状态表示：根据题目要求，dp[i]表示到达第i个位置时的总方法数
• 状态转移方程：根据题目要求得，从i - 1到i位置；从i - 2到i位置；从i - 3到i位置；所以 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
• 初始化：将前三个数初始化，防止越界（题目要求结果取模，在每次计算时都进行取模操作）
• 填表顺序：从左往右
• 返回值：dp[n]

C++代码

class Solution 
{
public:const int MOD = 1e9 + 7;int waysToStep(int n) {if(n == 1) return 1;if(n == 2) return 2;if(n == 3) return 4;vector<int> dp(n + 1);dp[1] = 1, dp[2] = 2, dp[3] = 4;for(int i = 4;i <= n; i++)dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3])% MOD;return dp[n];}
};

使用最小花费爬楼梯

题目：使用最小花费爬楼梯

思路1

• 状态表示：根据题目要求，dp[i]表示到达第i个位置时的最小花费；到达第i 个位置的时候，第 i 位置的花费不需要算上
• 状态转移方程：根据题目要求，dp[i] 由前两个状态转移得到。
  • 先到i - 1位置支付cost[i - 1]，走一步
  • 或者到i - 2位置支付cost[i - 2]，走一步
  • 两者取min，dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
• 初始化：dp[0] = dp[1] = 0
• 填表顺序：从左往右
• 返回值：dp[n]

C++代码1

class Solution 
{
public:int minCostClimbingStairs(vector<int>& cost){int n = cost.size();vector<int> dp(n + 1);// dp[0] = dp[1] = 0; vector默认不设置值时，里面都是0for (int i = 2; i <= n; i++){dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[n];}
};

思路2

• 状态表示：根据题目要求，dp[i]表示从第i个位置出发到达楼顶时的最小花费
• 状态转移方程：根据题目要求，dp[i] 由后两个状态转移得到。
  • 支付cost[i]，往后走一步，从i + 1到终点
  • 支付cost[i]，往后走两步，从i + 2到终点
  • dp[i] = min(cost[i] + dp[i + 1], cost[i] + dp[i + 2])
• 初始化：dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2]
• 填表顺序：从右到左
• 返回值：min(dp[0], dp[1])

C++代码2

class Solution 
{
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n, 0);dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];for (int i = n - 3; i >= 0; --i)dp[i] = min(cost[i] + dp[i + 1], cost[i] + dp[i + 2]);return min(dp[0], dp[1]);}
};

解码方法

题目：解码方法

思路

• 状态表示：根据题目要求，dp[i]表示，以i位置结尾的解码方法的总数
• 状态转移方程：根据最近一步划分
  • s[i]单独解码
    • 解码成功，即当s[i]是1-9之间，此时dp[i] += dp[i - 1]
    • 解码失败，0
  • s[i]和s[i - 1]结合解码
    • 解码成功，即当(s[i - 1] - '0') * 10 + s[i]是在10 - 26之间，此时dp[i] += dp[i - 2]
    • 解码失败，0
• 初始化：
  • dp[0]
    • s[i]是1-9之间，dp[0] = 1
    • s[i]是0，dp[0] = 0
  • dp[1]
    • s[i]是1-9之间，dp[1] += dp[0]
    • (s[i - 1] - '0') * 10 + s[i]``是在10 - 26之间，dp[1] += 1```
• 填表顺序：从左往右
• 返回值：dp[n]表示，以n - 1位置结尾的解码方法的总数

C++代码

class Solution 
{
public: int numDecodings(string s) {int n = s.size();vector<int> dp(n + 1);dp[0] = s[0] != '0';if(n == 1) return dp[0];if(s[0]!='0' && s[1]!='0') dp[1] += 1;    int t = (s[0] - '0') * 10 + s[1] - '0';if(t >= 10 && t <= 26)dp[1] += 1;for(int i = 2; i < n; i++){if(s[i] != '0') dp[i] += dp[i - 1];int t = (s[i - 1] - '0') * 10 + s[i] - '0';if(t >= 10 && t <= 26) dp[i] += dp[i - 2];}return dp[n - 1];}
};