做电影网站如何盈利,wordpress5.1更新,oa软件是什么,网站建设哪里好目录 一、做题心得
二、动规五步走
三、题目与题解
题目一#xff1a;509. 斐波那契数
题目链接
题解1#xff1a;记忆性递归 题解2#xff1a;动态规划
题目二#xff1a;70. 爬楼梯
题目链接
题解#xff1a;动态规划
题目三#xff1a;746. 使用最小花费爬楼…目录 一、做题心得
二、动规五步走
三、题目与题解
题目一509. 斐波那契数
题目链接
题解1记忆性递归 题解2动态规划
题目二70. 爬楼梯
题目链接
题解动态规划
题目三746. 使用最小花费爬楼梯
题目链接
题解动态规划
三、小结 一、做题心得
今天开始动态规划章节的第一部分。打卡的题目都比较基础也比较经典刚好作为入门。在最后一道题上会详细讲讲代码随想录中卡哥的动规五步走的确是很好的做题思路将代码的每一步都具象化。
话不多说直接开始今天的内容。
二、动规五步走
代码随想录中解决动态规划的五个步骤
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
对于简单的题可以直接解答复杂一点的按照这五步走可以使思路更加清晰。
三、题目与题解
题目一509. 斐波那契数
题目链接
509. 斐波那契数 - 力扣LeetCode 斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是 F(0) 0F(1) 1
F(n) F(n - 1) F(n - 2)其中 n 1给定 n 请计算 F(n) 。 示例 1 输入n 2
输出1
解释F(2) F(1) F(0) 1 0 1示例 2 输入n 3
输出2
解释F(3) F(2) F(1) 1 1 2示例 3 输入n 4
输出3
解释F(4) F(3) F(2) 2 1 3提示 0 n 30 题解1记忆性递归
为什么不直接用递归呢很显然直接递归的时间复杂度太高为了解决这个问题我们采用数组存储每个已经出现的数值这样就不需要每次都递归重新计算。
class Solution {
public:int fib(int n) {int dp[32]; //题目中 n 30, 可以直接一般数组如果是处理任意大小的n一般采用vector数组dp[0] 0, dp[1] 1;for (int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}; 题解2动态规划
思路由于 dp 列表第 i 项只与第 i−1 和第 i−2 项有关因此只需要选取三个整形变量 sum, dp[0], dp[1]分别代表这三个位置注意三者的初始化利用辅助变量 sum 使 dp[0], dp[1] 两数字交替前进即可。
代码如下
class Solution {
public:int fib(int n) {if (n 1) return n; //n 1时int dp[2];dp[0] 0;dp[1] 1;for (int i 2; i n; i) {int sum dp[0] dp[1]; //sum作为中间辅助变量记录第 i 项dp[0] dp[1]; //dp[0]记录 i - 2项dp[1] sum; //dp[1]记录 i - 1项 每次循环完成时记录第 i 项}return dp[1]; //n 2时}
};
题目二70. 爬楼梯
题目链接
70. 爬楼梯 - 力扣LeetCode 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 示例 1 输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶 示例 2 输入n 3
输出3
解释有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶提示 1 n 45 题解动态规划
其实这道题和斐波那契数列那道题思路是一样的只是值的初始化不同这里我只给出动态规划的解法。
class Solution {
public:int climbStairs(int n) {if (n 2) return n; //n 2时vectorint dp(n1);dp[1] 1;dp[2] 2;for (int i 3; i n 1; i) { int sum dp[1] dp[2];dp[1] dp[2];dp[2] sum;}return dp[2]; //n 3时}
};
题目三746. 使用最小花费爬楼梯
题目链接
746. 使用最小花费爬楼梯 - 力扣LeetCode 给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 示例 1 输入cost [10,15,20]
输出15
解释你将从下标为 1 的台阶开始。
- 支付 15 向上爬两个台阶到达楼梯顶部。
总花费为 15 。示例 2 输入cost [1,100,1,1,1,100,1,1,100,1]
输出6
解释你将从下标为 0 的台阶开始。
- 支付 1 向上爬两个台阶到达下标为 2 的台阶。
- 支付 1 向上爬两个台阶到达下标为 4 的台阶。
- 支付 1 向上爬两个台阶到达下标为 6 的台阶。
- 支付 1 向上爬一个台阶到达下标为 7 的台阶。
- 支付 1 向上爬两个台阶到达下标为 9 的台阶。
- 支付 1 向上爬一个台阶到达楼梯顶部。
总花费为 6 。提示 2 cost.length 10000 cost[i] 999 题解动态规划
今天主要想说的就是这道题。 这里我们按照动规五步走
1.定义dp[i]数组--注意dp[i]表示到达第i台阶所花费的最少费用为dp[i]
2.确定递推公式 得到dp[i]有两种方式前一个台阶处爬一步前两个台阶处爬两步 (1) dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] cost[i - 1]; (2) 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数组初始化题目要求可以从下标为 0 或下标为 1 的台阶开始爬楼梯即dp[0] 0, dp[1] 0 4.确定遍历顺序楼梯台阶这一类问题一般都是直接从前往后遍历 5.举例推导dp数组列举几个数看看满不满足
代码如下
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size(); //楼梯顶部的位置最后一个阶梯之外vectorint dp(n 1); dp[0] 0;dp[1] 0;for (int i 2; i n; i) {dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}return dp[n];}
};
三、小结
今天的打卡到此也就结束了动态规划的旅途还很漫长后边也会继续努力。
