哈尔滨网站建设30t,商用图片做公司网站可以吗,免费网站模板之家,网络平台推广运营有哪些平台文章目录 理论基础Leetcode 509-斐波那契数题目描述解题思路 Leetcode 70-爬楼梯题目描述解题思路 Leetcode 746-用最小花费爬楼梯题目描述解题思路 理论基础
动态规划#xff0c;简称 DP#xff0c;其中的每一个状态一定是由上一个状态推导出来的#xff0c;而贪心算法没有… 文章目录 理论基础Leetcode 509-斐波那契数题目描述解题思路 Leetcode 70-爬楼梯题目描述解题思路 Leetcode 746-用最小花费爬楼梯题目描述解题思路 理论基础
动态规划简称 DP其中的每一个状态一定是由上一个状态推导出来的而贪心算法没有状态推导只是从局部直接选最优。
动态规划的五步
确定 dp 数组以及下标的含义确定递推公式dp 数组如何初始化确定遍历顺序举例推导 dp 数组
Leetcode 509-斐波那契数
题目描述
https://leetcode.cn/problems/fibonacci-number/description/ 解题思路
class Solution {
public:int fib(int n) {vectorint dp(n1);dp[0] 0;if (n 0) dp[1] 1;for (int i 2; i n; i){dp[i] dp[i-1] dp[i-2];}return dp[n];}
};注意考虑 n0 的情况如果不加限制条件直接写 dp[1] 1 会报错因为数组越界
Leetcode 70-爬楼梯
题目描述
https://leetcode.cn/problems/climbing-stairs/description/ 解题思路
class Solution {
public:int climbStairs(int n) {vectorint dp(n);dp[0] 1;if (n1) dp[1] 2;for (int i 2; i n;i){dp[i] dp[i-1] dp[i-2];}return dp[n-1];}
};Leetcode 746-用最小花费爬楼梯
题目描述
https://leetcode.cn/problems/min-cost-climbing-stairs/description/ 解题思路
本题的解题思路继承爬楼梯在此基础上还需要考虑爬楼梯的费用
class Solution {
public:int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size());//dp保存的是到当前楼梯的最低花费int n cost.size();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]);}int minExpense min(dp[n-1]cost[n-1],dp[n-2]cost[n-2]);return minExpense;}
};
