情人节给女朋友做网站,很久以前做相册mv的网站,买房子最好的网站,微信调查问卷小程序怎么做动态规划理论基础
代码随想录 (programmercarl.com)
动态规划#xff08;Dynamic Programming#xff0c;简称DP#xff09;是一种算法设计技术#xff0c;它通过将复杂问题分解为更小的子问题来解决优化问题。动态规划通常用于解决那些具有重叠子问题和最优子结构特性的…动态规划理论基础
代码随想录 (programmercarl.com)
动态规划Dynamic Programming简称DP是一种算法设计技术它通过将复杂问题分解为更小的子问题来解决优化问题。动态规划通常用于解决那些具有重叠子问题和最优子结构特性的问题。可以理解为一种递推
重叠子问题 在递归算法中相同的子问题会被多次计算。动态规划通过存储这些子问题的解来避免计算。这个存储通常使用一个表格数组来实现称为备忘录或DP表。
最优子结构 一个问题的最优解包含其子问题的最优解。这意味着可以通过组合子问题的最优解来构造原问题的最优解。
动态规划的通常步骤
定义状态确定DP数组的含义即dp[i]通常代表什么意义比如在斐波那契数列问题中dp[i]代表第i个斐波那契数。状态转移方法确定状态之间如何转移即如何从一个或多个已知状态的值计算出下一个状态的值如斐波那契数中 F[i] F[i-1] F[i-2]。初始化确定DP数组的初始值这些通常关乎问题的边界条件。如斐波那契数中F[0] 0,F[1] 1。计算顺序确定DP数组的计算顺序通常需要按照逻辑顺序从小到大计算。如斐波那契数列需要一次从2开始向后计算得到想要的值。返回结果根据DP数组的最终值来确定原问题的解。如返回你需要的斐波那契数。 斐波那契数
509. 斐波那契数 - 力扣LeetCode
递推顺序为 F(n) F(n-1)F(n-2)
F(0) 0, F(1) 1
class Solution {
public:int fib(int n) {// 如果 n 小于或等于 1直接返回 n// 这是因为斐波那契数列的前两个数是定义好的F(0) 0, F(1) 1if(n1) return n;// 创建一个动态数组 dp大小为 n1用于存储斐波那契数列vectorintdp(n1);// 初始化 dp 数组的前两个数即 F(0) 和 F(1)dp[0] 0;dp[1] 1;// 从 2 开始循环到 n计算 dp 数组的其余值for(int i 2; i n; i){// 根据斐波那契数列的定义每个数是前两个数的和dp[i] dp[i-1] dp[i-2];}// 返回 dp 数组的最后一个值即斐波那契数列的第 n 个数return dp[n];}
};算法的时间复杂度为O(n)空间复杂度同样为O(n)需要维护一个斐波那契数数组。
爬楼梯
70. 爬楼梯 - 力扣LeetCode
斐波那契数的一个变体开始没想到想到之后只能感慨代码随想录的题目顺序还是很用心的。
假设爬到第i-1层有x种方案爬到第i-2层有y种方案那么爬到第i层有xy种方案(第i-1层再向上爬一层达到i第i-2层向上爬2层到达i层)。由此就能看出这个问题是上述斐波那契数的变体。递推关系为dp[i] dp[i-1] dp[i-2]从前往后遍历dp[0] 0,dp[1] 1爬到1层只有一种方案dp[2] 2爬到2层有2种可能 1 1 和 2。具体代码如下我考虑从3开始计算最后返回dp[n]。
class Solution {
public:// 定义一个名为 climbStairs 的函数用于计算爬到第 n 阶楼梯的方法数int climbStairs(int n) {// 如果 n 小于或等于 2直接返回 n// 这是因为当楼梯阶数不超过 2 时方法数与楼梯阶数相同if(n2) return n;// 创建一个动态数组 dp大小为 n1用于存储到达每一阶楼梯的方法数vectorintdp(n1);// 初始化 dp 数组的前三个数即到达第 0、1、2 阶的方法数// 到达第 0 阶的方法数为 0因为还没有开始爬,这里也可以认为是1能减少一点代码量 // 这样dp[2]不用赋值dp[0] 0;// 到达第 1 阶的方法数为 1只能爬 1 阶dp[1] 1;// 到达第 2 阶的方法数为 2可以一次爬 2 阶或者分两次各爬 1 阶dp[2] 2;// 从 3 开始循环到 n计算 dp 数组的其余值for(int i 3; i n; i){// 根据问题的性质到达第 i 阶的方法数是到达第 i-1 阶和第 i-2 阶的方法数之和// 这是因为每次你可以选择爬 1 阶或 2 阶所以到达第 i 阶的方法可以从第 i-1 阶爬上来或者从第 i-2 阶爬上来dp[i] dp[i-1] dp[i-2];}// 返回 dp 数组的最后一个值即到达第 n 阶的方法数return dp[n];}
};算法的时间复杂度为O(n)空间复杂度同样为O(n)需要维护一个斐波那契数数组。 使用最小花费爬楼梯
746. 使用最小花费爬楼梯 - 力扣LeetCode
这里同样是上述问题的变种但需要考虑的是这里不是找方案而是计算损失所以动态规划数组dp[i]代表的是到达n前的最小花费到达第i层需要分别计算到达第i-1层和到达第i-2层的损失然后选择较小的值作为dp[i]的值。由于在到达最终的n层前每次到达一个i都需要起跳所以需要添加损失dp[i]为min(dp[i-1]cost[i],dp[i-2]cost[i])而最后抵达n时不再需要起跳只需要考虑dp[n-1]和dp[n-2]的较小值就是爬楼梯所需的最小花费。
class Solution {
public:int minCostClimbingStairs(vectorint cost) {// 获取楼梯的阶数即成本数组的大小int n cost.size();// 创建一个动态数组 dp大小为 n用于存储到达每一阶楼梯的最小成本vectorintdp(n);// 初始化 dp 数组的前两个数即到达第 0、1 阶的最小成本// 到达第 0 阶的成本就是 cost[0]dp[0] cost[0];// 到达第 1 阶的成本就是 cost[1]dp[1] cost[1];// 从第 2 阶开始循环到第 n-1 阶计算 dp 数组的其余值for(int i 2; i n; i){// 到达第 i 阶的最小成本是到达第 i-1 阶和第 i-2 阶的最小成本加上当前阶梯的成本中的较小值// 这是因为每次你可以选择从第 i-1 阶爬上来或者从第 i-2 阶爬上来dp[i] min(dp[i-1] cost[i], dp[i-2] cost[i]);}// 最后到达楼顶的最小成本是到达倒数第一阶和倒数第二阶的最小成本中的较小值// 因为你可以从倒数第一阶直接到达楼顶也可以从倒数第二阶直接到达楼顶return min(dp[n-2], dp[n-1]);}
};算法的时间复杂度为O(n)遍历cost数组并计算得到dp数组空间复杂度同样为O(n)需要维护一个dp数组。
