509. 斐波那契数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
//动规五部曲
//1.确定dp数组以及下标的含义：
//第i个斐波那契数是dp[i]
//2.确定递推公式：dp[i] = dp[i - 1] + dp[i - 2];
//3.dp数组初始化：题目已给出
//4.遍历顺序：从前往后遍历
//5.举例推导：
//0 1 1 2 3 5 8 13
int fib(int n) {
if(n <= 1) return n;
vector<int> fi(n + 1);
//初始化
fi[0] = 0;
fi[1] = 1;
//遍历顺序
for(int i = 2; i <= n; i++)
{
fi[i] = fi[i - 1] + fi[i - 2];
}
return fi[n];
}
};
虽然是一道非常简单的题目，而且之前也做过，但没有从动规五部曲的角度去做，之后的dp题目要按照五部曲来刷~
动规五部曲
确定dp数组以及下标的含义
确定递推公式
dp数组初始化
遍历顺序
举例推导
70. 爬楼梯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
//动规五部曲
//1.确认dp数组和下标的含义
//爬到第i阶台阶的方法数为dp[i]
//2.确定递推公式
//dp[i] = dp[i - 1] + dp[i - 2]
//3.dp数组初始化
//4.遍历顺序：从前往后
//5.举例推导
//（从0阶开始）1 1 2 3 5 8 13
int climbStairs(int n) {
if(n == 1)return 1;
int dp[2];
//3.dp数组初始化
dp[0] = 1;
dp[1] = 1;
//4.遍历顺序：从前往后
for(int i = 2; i <= n; i++)
{
int tmp = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = tmp;
}
return dp[1];
}
};
这道题目本质上和斐波那契数列是一样的，只是递推公式没有给出，而是需要自己算，这次我换了中方式，没有创建n个长度的数组，只用两个空间的数组就可以了。