代码随想录算法训练营day32
代码随想录算法训练营—day32
前言
本日是算法营的第32天，盼望自己可以或许对峙下来！
开始动态规划章节了，本日使命：
● 动态规划理论底子
● 509. 斐波那契数
● 70. 爬楼梯
● 746. 使用最小耗费爬楼梯
一、动态规划理论底子
文章教学
视频教学
动态规划刷题大纲：
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvZjMyN2U1YzkxNjM4NDJlMGE5ZWQ2NzdjNDk5OWE3NjEucG5n
动态规划必要有一个推导公式，每一步都是由上一个状态推导出来的。
动态规划五步曲：
[*]确定dp数组以及下标的寄义
[*]确定递归公式
[*]dp数组怎样初始化
[*]确定遍历序次
[*]举例推导dp数组
做动规的标题，写代码之前肯定要把状态转移在dp数组的上具体情况模仿一遍，胸有定见，确定末了推出的是想要的效果。
二、509. 斐波那契数
标题链接
文章教学
视频教学
思绪：
[*]dp的界说为：第i个数的斐波那契数值是dp
[*]递归公式：标题已经把递推公式直接给我们了：dp = dp + dp
[*]初始化：dp = 0, dp = 1
[*]遍历序次:由于递推公式是从前去后的，以是遍历序次是从前去后
动态规划
代码如下：
class Solution {
public:
//动态规划
//dp就是第i个斐波那契数
//递推公式：dp = dp + dp;
//初始化：dp = 0, dp = 1
//遍历顺序：从头到尾
int fib(int n) {
if (n <= 1) return n;
vector<int> dp(n+1);
dp = 0;
dp = 1;
for(int i = 2; i <=n; i++) {
dp = dp + dp;
}
return dp;
}
};
动态规划优化空间版
由于效果只由前两项决定，以是不必要维护数组，只必要维护三个变量
代码如下：
class Solution {
public:
//动态规划
//dp就是第i个斐波那契数
//递推公式：dp = dp + dp;
//初始化：dp = 0, dp = 1
//遍历顺序：从头到尾
int fib(int n) {
if (n <= 1) return n;
//因为结果只由前两项决定，所以不需要维护数组，只需要维护三个变量
int dp;
dp = 0; //f
dp = 1; //f
for(int i = 2; i <=n; i++) {
int sum = dp + dp; //f = f + f
dp = dp; //更新f
dp = sum; //更新f
}
return dp;
}
};
递归法
这道题也可以用递归法，代码更加简便：
class Solution {
public:
//递归法
int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
};
三、70. 爬楼梯
标题链接
文章教学
视频教学
动态规划
思绪：
[*]dp的界说为： 爬到第i层楼梯，有dp种方法
[*]递归公式：由于dp都是由i-1走一层大概i-2走两层到达的，而dp就是走到i-1层的方法，dp就是走到i-2层的方法，那么走到i层就是dp + dp种方法。
dp = dp + dp;
[*]初始化：dp = 1，dp = 2，dp没有寄义，标题也说了n是大于0的，以是递推从1开始，初始化1,2，遍历从3开始。
[*]遍历序次:由于递推公式是从前去后的，以是遍历序次是从前去后
[*]举例推导dp数组：
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMjhiMzk1MmJhYjE2NGZmOTgzYzllNzRkOGYzNTllODMucG5n
代码如下：
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
vector<int> dp(n + 1); //需要初始化大小
dp = 1;
dp = 2;
for (int i = 3; i <= n; i++) {
dp = dp + dp;
}
return dp;
}
};
动态规划空间优化
这道题也是只跟i-1和i-2有关，以是只必要维护3个变量就可以了。
代码如下：
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
int dp; //优化空间
dp = 1;
dp = 2;
for (int i = 3; i <= n; i++) {
int sum = dp + dp;
dp = dp;
dp = sum;
}
return dp;
}
};
746. 使用最小耗费爬楼梯
标题链接
文章教学
视频教学
思绪：
[*]dp的界说为：代表走到第i台阶必要耗费多少
[*]递归公式：第i台阶通过第i-1台阶走一步大概第i-2台阶走两步到达，取两者耗费最小为最优解dp = min(dp + cost, dp + cost);
[*]初始化：默认第一步不耗费体力，第一步从下标0大概1开始， dp = 0, dp = 0
[*]遍历序次:由于递推公式是从前去后的，以是遍历序次是从前去后
代码如下：
class Solution {
public:
//d含义：代表走到第i台阶需要花费多少
//递推公式，第i台阶通过第i-1台阶走一步或者第i-2台阶走两步到达，取两者花费最小为最优解
int minCostClimbingStairs(vector<int>& cost) {
if (cost.size() < 2) return 0;
vector<int> dp(cost.size() + 1);
dp = 0; //默认第一步不花费体力
dp = 0;
for (int i = 2; i <= cost.size(); i++) {
dp = min(dp + cost, dp + cost);
}
return dp;
}
};
动态规划空间优化
同样可以优化空间：
class Solution {
public:
//d含义：代表走到第i台阶需要花费多少
//递推公式，第i台阶通过第i-1台阶走一步或者第i-2台阶走两步到达，取两者花费最小为最优解
int minCostClimbingStairs(vector<int>& cost) {
if (cost.size() < 2) return 0;
int dp; //优化空间
dp = 0; //默认第一步不花费体力
dp = 0;
for (int i = 2; i <= cost.size(); i++) {
int sum = min(dp + cost, dp + cost);
dp = dp;
dp = sum;
}
return dp;
}
};
总结
动态规划第一天！第一次打仗动态规划，牢记动态规划五步曲：
[*]确定dp数组以及下标的寄义
[*]确定递归公式
[*]dp数组怎样初始化
[*]确定遍历序次
[*]举例推导dp数组
一些小总结：
[*]想不明白的时间必要回归dp数组下标寄义再明白一下。
[*]初始化的时间假如遇到像是dp没有寄义的时间，试试从反面的dpdp比力明白初始化的下标开始初始化和递推。
[*]当递推公式只涉及i-1,i-2的时间，可以缩小数组巨细，只维护最小的数组来节流空间。
来日诰日继承加油！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]