亦庄网站开发,佛山市专注网站建设平台,网站建设方案的企业,国内免费无版权图片素材网站动态规划理论
动态规划#xff0c;Dynamic Programming#xff0c; DP#xff0c; 如果某一问题有很多重叠子问题#xff0c;使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的#xff0c;这一点就区分于贪心#xff0c;贪心没有状态推导…动态规划理论
动态规划Dynamic Programming DP 如果某一问题有很多重叠子问题使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的
状态转移公式递推公式是很重要但动规不仅仅只有递推公式。
对于动态规划问题我将拆解为如下五步曲这五步都搞清楚了才能说把动态规划真的掌握了
确定dp数组dp table以及下标的含义确定递推公式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) 。
思路
动规五部曲
这里我们要用一个一维dp数组来保存递归的结果
确定dp数组以及下标的含义 dp[i]的定义为第i个数的斐波那契数值是dp[i]确定递推公式 状态转移方程 dp[i] dp[i - 1] dp[i - 2]dp数组如何初始化 dp[0] 0; dp[1] 1;确定遍历顺序从前向后遍历举例推导 根据公式当n10时数列为0 1 1 2 3 5 8 13 21 34 55
class Solution {
public:int fib(int n) {if (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];}
};
70. 爬楼梯
题目要求
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
思路
上第i个台阶的方法数上第i-1个台阶的方法数爬1个台阶上第i-2个台阶的方法数爬2个台阶
class Solution {
public:int climbStairs(int n) {if (n1) return n;int dp[3];dp[1] 1;dp[2] 2;for (int i 3; i n; i) {int sum dp[1] dp[2];dp[1] dp[2];dp[2] sum;}return dp[2];}
};
746. 使用最小花费爬楼梯
题目要求数组的每个下标作为一个阶梯第 i 个阶梯对应着一个非负数的体力花费值 cost[i]下标从 0 开始。
每当你爬上一个阶梯你都要花费对应的体力值一旦支付了相应的体力值你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时你可以选择从下标为 0 或 1 的元素作为初始阶梯。
思路
修改之后的题意就比较明确了题目中说 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于 跳到 下标 0 或者 下标 1 是不花费体力的 从 下标 0 下标1 开始跳就要花费体力了。
确定dp数组以及下标的含义
使用动态规划就要有一个数组来记录状态本题只需要一个一维数组dp[i]就可以了。
dp[i]的定义到达第i台阶所花费的最少体力为dp[i]。
确定递推公式
可以有两个途径得到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;
确定遍历顺序
因为是模拟台阶而且dp[i]由dp[i-1]dp[i-2]推出所以是从前到后遍历cost数组就可以了。
举例推导dp数组
拿示例2cost [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 来模拟一下dp数组的状态变化如下 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()];}
};
时间复杂度O(n)空间复杂度O(n)还可以优化空间复杂度因为dp[i]就是由前两位推出来的那么也不用dp数组了优化方法和上一题同理。
