网站开发pdf,重庆网站建设项目,智能网站建设哪家效果好,自己做的表白网站什么是动态规划
对于动态规划问题#xff0c;我将拆解为如下五步曲#xff0c;这五步都搞清楚了#xff0c;才能说把动态规划真的掌握了#xff01;
确定dp数组#xff08;dp table#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组我将拆解为如下五步曲这五步都搞清楚了才能说把动态规划真的掌握了
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组打印dp数组
找问题的最好方式就是把dp数组打印出来看看究竟是不是按照自己思路推导的
做动规的题目写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍心中有数确定最后推出的是想要的结果。
509 斐波那契数
题目描述
斐波那契数 通常用 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
题目分析
就像二叉树三部曲 确定递归函数的参数和返回值 确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 确定终止条件 写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。 确定单层递归的逻辑 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
是有方法论的
这里动规五步曲也是一样
acm模式代码
#include iostream
#include vectorclass Solution {
public:int fib(int n) {std::vectorint dp(n 1);if (n 0) {return 0;}else 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];}
};int main() {Solution sol;int n 5;int sum sol.fib(n);std::cout n sum: sum std::endl;return 0;
} 70. 爬楼梯
题目描述
假设你正在爬楼梯。需要 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
题目分析 爬到第一层楼梯有一种方法爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来那么就可以想到动态规划了。
acm模式代码
#include iostream
#include vectorclass Solution {
public:int climbStairs(int n) {if (n 1) return n;std::vectorint 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];}
};int main() {Solution sol;int n 5;int sum sol.climbStairs(n);std::cout n sum: sum std::endl;return 0;
}
746使用最小花费爬楼梯
题目描述 给你一个整数数组 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 题目分析
确定dp数组以及下标的含义
使用动态规划就要有一个数组来记录状态本题只需要一个一维数组dp[i]就可以了。
dp[i]的定义到达第i台阶所花费的最少体力为dp[i]。
对于dp数组的定义大家一定要清晰
确定递推公式
可以有两个途径得到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 - 1]跳还是从dp[i - 2]跳呢
一定是选最小的所以dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);
dp数组如何初始化
看一下递归公式dp[i]由dp[i - 1]dp[i - 2]推出既然初始化所有的dp[i]是不可能的那么只初始化dp[0]和dp[1]就够了其他的最终都是dp[0]dp[1]推出。
那么 dp[0] 应该是多少呢 根据dp数组的定义到达第0台阶所花费的最小体力为dp[0]那么有同学可能想那dp[0] 应该是 cost[0]例如 cost [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 的话dp[0] 就是 cost[0] 应该是1。
这里就要说明本题力扣为什么改题意而且修改题意之后 就清晰很多的原因了。
新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的但从 第0 个台阶 往上跳的话需要花费 cost[0]。
所以初始化 dp[0] 0dp[1] 0;
确定遍历顺序
最后一步递归公式有了初始化有了如何遍历呢
本题的遍历顺序其实比较简单简单到很多同学都忽略了思考这一步直接就把代码写出来了。
acm模式代码
#include iostream
#include vector
#include algorithmclass Solution {
public:int minCostClimbingStairs(std::vectorint cost) {std::vectorint dp(cost.size() 1);// dp[i]的定义到达第i台阶所花费的最少体力为dp[i]。dp[0] 0;dp[1] 0;int sum 0;for (int i 2; i cost.size(); i) {dp[i] std::min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}// for (int i : dp) {// std::cout i ;// }// std::cout std::endl;// return dp.back();return dp[cost.size()];}
};int main() {std::vectorint count {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};Solution sol;int min sol.minCostClimbingStairs(count);std::cout sum: min std::endl;
}
