当前位置:   article > 正文

动态规划基础

动态规划基础

动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。动态规划中每一个状态一定是由上一个状态推导出来的。区分于贪心,贪心没有状态推导,而是从局部直接选最优的,

动态规划中dp[j]是由dp[j-weight[i]]推导出来的,然后取max(dp[j], dp[j - weight[i]] + value[i])。

如果是贪心呢,每次拿物品选一个最大的或者最小的就完事了,和上一个状态没有关系。所以贪心解决不了动态规划的问题。

动态规划的解题步骤

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

递推公式决定了dp数组要如何初始化 ,

 1. 基础题目

1.1 509. 斐波那契数

斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给你n ,请计算 F(n) 。

示例 1:

  • 输入:2
  • 输出:1
  • 解释:F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2:

  • 输入:3
  • 输出:2
  • 解释:F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3:

  • 输入:4
  • 输出:3
  • 解释:F(4) = F(3) + F(2) = 2 + 1 = 3

提示:

  • 0 <= n <= 30

思路分析:

首先定义一个一个一维dp数组来保存递归的结果

1. 确定dp数组以及下标的含义

dp[i]的定义为:第i个数的斐波那契数值是dp[i]

2. 确定递推公式

此处递推公式已经给了dp[i]=dp[i-1]+dp[i-2];

3.dp数组初始化

 题目已经给了dp[0]=0,dp[1]=1;

4. 确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的

5.举例推导dp数组

当N为10的时候,dp数组应该是如下的数列:

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来,发现结果不对,就把dp数组打印出来看看和我们推导的数列是不是一致的。

  1. int fib(int n) {
  2. if (n <= 1) return n; // 防止数组越界
  3. vector<int>dp(n + 1); // 注意边界,dp[n]对应n+1个元素
  4. dp[0] = 0;
  5. dp[1] = 1;
  6. for (int i = 2; i < n; i++) { // 从前往后遍历
  7. dp[i] = dp[i - 1] + dp[i - 2];
  8. }
  9. return dp[n];
  10. }
  11. };

2. 70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

  • 输入: 2
  • 输出: 2
  • 解释: 有两种方法可以爬到楼顶。
    • 1 阶 + 1 阶
    • 2 阶

示例 2:

  • 输入: 3
  • 输出: 3
  • 解释: 有三种方法可以爬到楼顶。
    • 1 阶 + 1 阶 + 1 阶
    • 1 阶 + 2 阶
    • 2 阶 + 1 阶

1. 确定dp数组以及下标的含义

dp[i]的定义为: 爬到第n阶楼梯有dp[i]种方法

2. 确定递推公式

因为一次只能爬两层,所以dp[i]要么是从i-1层来,要么是从i-2层来,上i-1层楼梯,有dp[i - 1]种方法,上i-2层楼梯,有dp[i - 2]种方法,dp[i]就是 dp[i - 1]与dp[i - 2]之和,所以dp[i] = dp[i - 1] + dp[i - 2] 。

3.dp数组初始化

 上一层楼只有一种方法dp[1]=1;上两层楼可以一步到,也可以分两步到,共有两种方法,dp[2]=2;

4. 确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的

5.举例推导dp数组

当N为10的时候,dp数组应该是如下的数列:

 1 2 3 5 8 13 21 34 55

  1. int climbStairs(int n) {
  2. if (n <= 1) return n; // 防止越界
  3. vector<int> dp(n + 1);
  4. dp[1] = 1;
  5. dp[2] = 2;
  6. for (int i = 3; i <= n; i++) { // 注意i是从3开始的
  7. dp[i] = dp[i - 1] + dp[i - 2];
  8. }
  9. return dp[n];
  10. }

扩展:如果是一步一个台阶,两个台阶,三个台阶,直到 m个台阶,有多少种方法爬到n阶楼顶。

  1. class Solution {
  2. public:
  3. int climbStairs(int n) {
  4. vector<int> dp(n + 1, 0);
  5. dp[0] = 1; // 必须从0开始代表各结点从原点出发直接一步到达dp[i]
  6. for (int i = 1; i <= n; i++) {
  7. for (int j = 1; j <= m; j++) {
  8. if (i - j >= 0) dp[i] += dp[i - j];
  9. }
  10. }
  11. return dp[n];
  12. }
  13. };

3. 746. 使用最小花费爬楼梯

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1:

输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。

示例 2:

输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
解释:你将从下标为 0 的台阶开始。
- 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
- 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
- 支付 1 ,向上爬一个台阶,到达楼梯顶部。
总花费为 6 。

提示:

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

  1. 确定dp数组以及下标的含义

使用动态规划,就要有一个数组来记录状态,本题只需要一个一维数组dp[i]就可以了。

dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]

 2.确定递推公式

可以有两个途径得到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]);

 3.dp数组如何初始化

看一下递归公式,dp[i]由dp[i - 1],dp[i - 2]推出,那么只初始化dp[0]和dp[1]就够了,其他的最终都是dp[0],dp[1]推出。题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的,所以初始化 dp[0] = 0,dp[1] = 0;

 4. 确定遍历顺序

dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了。

  1. 举例推导dp数组

拿示例2:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,来模拟一下dp数组的状态变化,如下:

0 0 1 2 2 3 3 4 4 5 6

  1. int minCostClimbingStairs(vector<int>& cost) {
  2. vector<int> dp(cost.size() + 1);
  3. dp[0] = 0; // 默认第一步都是不花费体力的
  4. dp[1] = 0;
  5. for (int i = 2; i <= cost.size(); i++) {
  6. dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
  7. }
  8. return dp[cost.size()];
  9. }

01 背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

1.确定dp数组以及下标的含义

dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

2. 确定递推公式

有两个方向推出来dp[i][j],

  • 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以背包内的价值依然和前面相同。)
  • 放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值

所以递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.dp数组如何初始化

如果背包容量j为0的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为0。

、状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来,那么i为0的时候就一定要初始化。

dp[0][j],即:i为0,存放编号0的物品的时候,各个容量的背包所能存放的最大价值。

那么很明显当 j < weight[0]的时候,dp[0][j] 应该是 0,因为背包容量比编号0的物品重量还小。

当j >= weight[0]时,dp[0][j] 应该是value[0],因为背包容量放足够放编号0物品。

  1. for (int j = 0 ; j < weight[0]; j++) { // 当然这一步,如果把dp数组预先初始化为0了,这一步就可以省略,但很多同学应该没有想清楚这一点。
  2. dp[0][j] = 0;
  3. }
  4. // 正序遍历
  5. for (int j = weight[0]; j <= bagweight; j++) {
  6. dp[0][j] = value[0];
  7. }

从递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了,那么 其他下标初始为什么数值都可以,因为都会被覆盖。

最终

  1. vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
  2. for (int j = weight[0]; j <= bagweight; j++) {
  3. dp[0][j] = value[0];
  4. }
  1. 确定遍历顺序

在如下图中,可以看出,有两个遍历的维度:物品与背包重量

先遍历物品,然后遍历背包重量的代码。

  1. // weight数组的大小 就是物品个数
  2. for(int i = 1; i < weight.size(); i++) { // 遍历物品
  3. for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
  4. if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 装不下
  5. else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  6. }
  7. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/144245
推荐阅读
相关标签
  

闽ICP备14008679号