动态规划的简单套路（C++描述）

动态规划

作者：Cukor丘克

通过例子学习动态规划。动态规划是解决递归重复计算的方法。

能解决的问题：

1. 计数
2. 最值
3. 存在性

解题步骤：

1. 最后一步
2. dp数组的含义
3. 状态转移方程
4. dp数组的初始化
5. 实例代入

使用的编程语言的是C++.

引导

斐波那契数列

什么是斐波那契数列？

前两个数字是1，从第3个数开始，是它的前两个数之和。

代码实现：

递归方式：

int fib(int n){
   
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fib(n-1) + fib(n-2);
}
1
2
3
4
5
6

动态规划：

// 最后一步：前面的数据已经算好，最后一个数据只需要拿到它的前两个数据即可。
// dp数组的含义：第i个数的斐波那契数是dp[i]
// 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
// dp数组的初始化：dp[0] = 0; dp[1] = 1;
// 实例代入：dp[5] = dp[4] + dp[3];
//            dp[4] = dp[3] + dp[2];    dp[3] = dp[2] + dp[1];        
//            dp[2] = dp[1] + dp[0];    
// 过程：dp[5] = 5;
//            dp[4] = 3    dp[3] = 2;        
//            dp[2] = 1;
int fib(int n) {
   
    if (n <= 1) return n;
    vector<int> dp(n+1);
    dp[0] = 0; 
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
   
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

计数

• 爬楼梯
• 机器人走路

爬楼梯：你爬楼梯，你可以一次走一步，也一次可以走两个。现有n阶楼梯，你有多少种方法爬到顶部。

/*
最后一步：要么第n-1阶，要么n-2阶,只需要知道走到n-1阶有多少种方法，和走到n-2阶有多少种方法。

dp数组的含义：走到n阶楼梯的方法数是dp[n]

状态转移方程：dp[n] = dp[n-1] + dp[n-2]

初始化：dp[1] = 1; dp[2] = 2; 
*/
int climb_stairs(int n) {
   
    if (n <= 1)
        return n;
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15