刷题的第二十六天，希望自己能够不断坚持下去，迎来蜕变。😀😀😀
刷题语言：C++
Day26 任务
● 动态规划理论基础
● 斐波那契数
● 爬楼梯
● 使用最小花费爬楼梯
1 动态规划理论基础
对于动态规划问题，拆解为五个步骤：
（1）确定dp数组以及下标的含义
（2）确定递推公式
（3）dp数组如何初始化
（4）遍历顺序
（5）举例推导dp数组
2 斐波那契数
斐波那契数
思路：
递归法
C++：
class Solution {
public:
int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
};
时间复杂度：
O
(
2
n
)
O(2^n)
O(2n)
空间复杂度：
O
(
n
)
O(n)
O(n)
动态规划
用一个一维的dp数组保存递归的结果
（1）确定dp数组以及下标的含义
dp[i]的定义为：第i个数的斐波那契数值是dp[i]
（2）确定递推公式
状态转移方程：
d
p
[
i
]
=
d
p
[
i
−
1
]
+
d
p
[
i
−
2
]
dp[i] = dp[i - 1] + dp[i - 2]
dp[i]=dp[i−1]+dp[i−2]
（3）dp数组如何初始化
dp[0] = 0;
dp[1] = 1;
（4）遍历顺序
dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
（5）举例推导dp数组
把dp数组打印出来看看和我们推导的数列是不是一致的
C++：
class Solution {
public:
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];
}
};
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
本题只需要维护两个数值
C++：
class Solution {
public:
int fib(int n) {
if (n <= 1) return n;
int dp[2];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
int sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
};
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)
3 爬楼梯
爬楼梯
思路：
动态规划
（1）确定dp数组以及下标的含义
dp[i]： 爬到第i层楼梯，有dp[i]种方法
（2）确定递推公式
dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶就是dp[i]
dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶就是dp[i]
d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] dp[i] = dp[i - 1] + dp[i - 2] dp[i]=dp[i−1]+dp[i−2]
（3）dp数组如何初始化
dp[0] = 1;
dp[1] = 1;
（4）遍历顺序：从前往后
（5）举例推导dp数组
C++:
class Solution {
public:
int climbStairs(int n) {
if (n <= 1) return n;
vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
优化代码：
class Solution {
public:
int climbStairs(int n) {
if (n <= 1) return n;
int dp[3];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
int sum = dp[1] + dp[2];
dp[1] = dp[2];
dp[2] = sum;
}
return dp[2];
}
};
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)
4 使用最小花费爬楼梯
使用最小花费爬楼梯
思路：
动态规划
可以选择从下标为0或下标为1的台阶开始爬楼梯就是相当于跳到下标 0或者下标1是不花费体力的， 从 下标 0 下标1 开始跳就要花费体力了
（1）确定dp数组以及下标的含义
dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]
（2）确定递推公式
有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]
dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]
dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
（3）dp数组如何初始化
dp[0] = 0;
dp[1] = 0;
（4）遍历顺序：从前到后遍历cost数组
（5）举例推导dp数组
C++：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size() + 1);
dp[0] = 0;// 默认第一步都是不花费体力的
dp[1] = 0;
for (int i = 2; i <= cost.size(); i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.size()];
}
};
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
优化：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int dp0 = 0;
int dp1 = 0;
for (int i = 2; i <= cost.size(); i++) {
int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
dp0 = dp1; // 记录一下前两位
dp1 = dpi;
}
return dp1;
}
};
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)
鼓励坚持二十七天的自己😀😀😀
