代码随想录算法训练营第三十二天 | 动态规划 part01
动态规划基础
动态规划题目类型
- 动规基础题
- 背包问题
- 打家劫舍
- 股票问题
- 子序列问题
动规5部曲
- dp数组定义以及下标含义
- 递推公式
- dp数组初始化
- 遍历顺序
- 打印dp数组查找问题
509. 斐波那契数
按照五部曲进行分析：
- dp数组的含义是dp[i]就是F(i)
- dp[i] = dp[i - 1] + dp[i - 2]
- dp[0]=0,dp[1]=1
- 从前向后遍历
class Solution {
public:int fib(int n) {vector<int> dp(n + 1);if (n == 0)return 0;if (n == 1)return 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];}
};
70. 爬楼梯
动态规划的题目要去找递推函数，其实就是找规律。可以发现本题的规律就是斐波那契数列。
- dp[i]含义是爬到第i级台阶有多少种方法
- 递推函数：dp[i] = dp[i - 1] + dp[i - 2]。爬到第i阶只要从i-1爬一级或i-2爬两级
- dp初始化，dp[1]=1,dp[2]=2
- 遍历顺序：从前向后
class Solution {
public:int climbStairs(int n) {vector<int> dp(n + 1);if (n == 1)return 1;if (n == 2)return 2;dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; ++i) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};
746. 使用最小花费爬楼梯
- dp[i]含义是到达第i层台阶要花费多少，i的取值范围是[0, n]，其中n就是楼顶
- 递推函数：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
- dp初始化，dp[0]=0,dp[1]=0
- 遍历顺序：从前向后
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n + 1, 0);for (int i = 2; i < n + 1; ++i) {dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[n];}
};