网站建设算什么专业,做网站设计素材,优秀网页设计网站,手机网站建设软件有哪些碎碎念#xff1a;开始动态规划了#xff01;加油#xff01; 参考#xff1a;代码随想录
动态规划理论基础
动态规划常见类型#xff1a;
动规基础类题目背包问题打家劫舍股票问题子序列问题
解决动态规划问题应该要思考清楚的#xff1a; 动态规划五部曲#xff1…碎碎念开始动态规划了加油 参考代码随想录
动态规划理论基础
动态规划常见类型
动规基础类题目背包问题打家劫舍股票问题子序列问题
解决动态规划问题应该要思考清楚的 动态规划五部曲
dp数组以及它下标的含义递推公式dp数组如何初始化遍历顺序打印dp数组
509. 斐波那契数
题目链接
509. 斐波那契数
思想
动态规划五部曲
确定dp数组以及下标的含义dp[i] 第i个斐波那契数确定递推公式dp[i] dp[i-1]dp[i-2]dp数组的初始化dp[0]1 dp[1]1确定遍历顺序从前向后遍历打印dp数组主要用来debug
由于求一个值只依赖前两个值所以我们没必要维护一个数组可以维护三个变量来完成状态转移。见python代码。
题解
// cpp
class Solution {
public:int fib(int n) {if (n 0 || n 1) return n;vectorint dp(n1);dp[0] 0;dp[1] 1;for (int i 2; i n; i) {dp[i] dp[i-1] dp[i-2];}return dp[n];}
};# python
class Solution:def fib(self, n: int) - int:if n 1:return nprev1, prev2 0, 1for _ in range(2, n1):cur prev1 prev2prev1, prev2 prev2, curreturn prev2反思
本题简单是因为题中已经给出了递推公式和初始值。
70. 爬楼梯
题目链接
70. 爬楼梯
思想
动态规划五部曲
确定dp数组以及下标的含义dp[i] 表示达到i阶梯有dp[i]种方法确定递推公式dp[i] dp[i-1]dp[i-2] 爬到第i阶时要么是从i-1一步过来的要么从i-2一步迈两阶过来的dp数组的初始化dp[0]0 dp[1]1dp[0]的取法主要是为了使得dp[2]为2从含义上来说到达0阶应该0种方法也可以初始化dp[1]1dp[2]2不初始化dp[0]确定遍历顺序从前向后遍历打印dp数组主要用来debug
和上一题同理也可以优化掉dp数组。
题解
// cpp
class Solution {
public:int climbStairs(int n) {if (n 1) return n;vectorint dp(n1);dp[1] 1;dp[2] 2;for (int i 3; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
};# python
class Solution:def climbStairs(self, n: int) - int:if n 1:return nprev1 1prev2 2for _ in range(3, n 1):cur prev1 prev2prev1, prev2 prev2, curreturn prev2反思
注意初始化那部分。
746. 使用最小花费爬楼梯
题目链接
746. 使用最小花费爬楼梯
思想
注意站在某个位置不花费cost要爬上台阶的时候才会花费cost。 如图所示顶楼应该在3的位置。 动态规划五部曲
确定dp数组以及下标的含义dp[i] 表示达到下标i的位置所需要的最小花费确定递推公式dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])dp数组的初始化dp[0]0 dp[1]0确定遍历顺序从前向后遍历打印dp数组主要用来debug
和上一题同理也可以优化掉dp数组。
题解
// cpp
class Solution {
public:int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size() 1);dp[0] 0;dp[1] 0;for (int i 2; i cost.size(); i) {dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}return dp[cost.size()];}
};# python
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:prev1 0prev2 0for i in range(2, len(cost) 1):cur min(prev1 cost[i - 2], prev2 cost[i - 1])prev1, prev2 prev2, curreturn prev2
反思
