【学习路线】

  1. 对动态规划有一个初步的了解，只看问题引入的部分：什么是动态规划？动态规划的意义是什么？
  2. B站的UP主动态规划入门课，通俗易懂：动态规划第一讲
  3. 动态规划第二讲的第一题
  4. 一位博主，总结的很不错：告别动态规划，DP连刷 40 道题，我总结出了这些套路！这应该是把动态规划讲的最后的文章了
  5. 动态规划第二讲第二题
  6. 二维dp问题：01背包问题

dp引入：换钱（一维dp）

原文链接：什么是动态规划？动态规划的意义是什么？)

【问题】你想把某宝里的666块换成现金，而且想换来的钱的总数最少，因为你的钱包快装不下了

【生活中的做法】从最大的面额开始换，以此可以获得数量最少的钞票，共10张。这种思想叫贪心，每经过一次，它会尽量让数值变得更小

动态规划 - 图1

【贪心的方法是对的吗？】如果钱的面额够科学，贪心就是对的。但是遇到这种情况：一个国家的钞票面额只有1、5、11。那我们这次用贪心来换15块

  1. 动态规划 - 图2，用贪心换得5张钞票
  2. 动态规划 - 图3，但最少的情况是这个，换得3张钞票

【贪心错在哪里？】鼠目寸光，只考虑了眼前的情况

【解决方案】我们用f(n)表示换n块所需的最小钞票的数量，那我们就有以下的情况

  1. 动态规划 - 图4%3D1#card=math&code=f%281%29%3D1&id=HPyn9)：换1块钱，就只要一张1块
  2. 动态规划 - 图5%3D4#card=math&code=f%284%29%3D4&id=IuD3I)：换4块钱，要4张1块
  3. 动态规划 - 图6%3D1#card=math&code=f%285%29%3D1&id=pNOHZ)：换5块钱，就只要1张5块
  4. 动态规划 - 图7%3D2#card=math&code=f%2810%29%3D2&id=yxXZ7)：换10块钱，要2张5块
  5. 动态规划 - 图8%3D1#card=math&code=f%2811%29%3D1&id=qy13o)：换11块钱，就只需要1张11块

理解的话，我们来换一下15块

  1. 动态规划 - 图9%3Df(11)%2Bf(4)%3D1%2B4%3D5#card=math&code=cost%2815%29%3Df%2811%29%2Bf%284%29%3D1%2B4%3D5&id=Is7sj)：这种策略要5张
  2. 动态规划 - 图10%3Df(5)%2Bf(10)%3Df(5)%2Bf(5)%2Bf(5)%3D3#card=math&code=cost%2815%29%3Df%285%29%2Bf%2810%29%3Df%285%29%2Bf%285%29%2Bf%285%29%3D3&id=RIORD)：这种策略要3张
  3. 动态规划 - 图11%3Df(1)%2Bf(14)%3D1%2B4%3D5#card=math&code=cost%2815%29%3Df%281%29%2Bf%2814%29%3D1%2B4%3D5&id=AUhKc)：这种策略只要5张

那我们要的就是3个中最小的情况，于是有公式：

f(n)=min{ f(n-1), f(n-5), f(n-11) } +1

有了这个公式怎么暴力求解呢？

  1. int f_0(int n) { //用递归暴力求解
  2.     int mincost = 65535;
  3.     if (n==0) return 0;
  4.     if (n>=1) mincost = min(mincost, f_0(n-1)+1);
  5.     if (n>=5) mincost = min(mincost, f_0(n-5)+1);
  6.     if (n>=11) mincost = min(mincost, f_0(n-11)+1);
  8.     printf("f[n]=%d\n", n, mincost);
  9.     return mincost;
  10. }

此过程会生成一个递归树，由于最小面额为1，所以树的高度为n，则把树当成满二叉树来算结点总数动态规划 - 图12，故此方法的时间复杂度为动态规划 - 图13#card=math&code=O%282%5En%29&id=RCA7f)

动态规划 - 图14

改良1：用数组保存之前的计算结果，避免重复计算，复杂度O(n)。这就是dp，暂时可以把dp理解成用数组记录历史记录的递归或递推

int min(int a, int b) {
    return a>b?b:a;
}
int f_1(int n) { 
    int i, mincost, f[105];
    f[0]=0;
    for (i=1; i<=n; ++i) { //递推的方式：从下往上算
        mincost = 65535;
        if (i>=1) mincost = min(mincost, f[i-1]+1);
        if (i>=5) mincost = min(mincost, f[i-5]+1);
        if (i>=11) mincost = min(mincost, f[i-11]+1);
        f[i]=mincost;
    }
    return f[n];
}


f[105]={0};         //把每次计算的值保存下来
int f_2(int n) { //递归的方式：从上往下找需要算的内容
    int mincost = 65535;

    if (n==0) return 0;

    if (n>=1) mincost = min(mincost, f[n-1]==0 ? f_2(n-1)+1: f[n-1]+1 );
                                        //看f[n-1]之前有没有算过（有个装逼名字叫：记忆化搜索）
    if (n>=5) mincost = min(mincost, f[n-5]==0 ? f_2(n-5)+1: f[n-5]+1 );
    if (n>=11) mincost = min(mincost, f[n-11]==0 ? f_2(n-11)+1: f[n-11]+1 );

    f[n]=mincost;
    printf("f[%d]=%d\n", n, f[n]); //看到底计算了谁
    return mincost;
}

对比：暴力<动态规划<贪心（从效率和使用条件的角度）

  1. 【贪心】上面所提，贪心的问题在于鼠目寸光，但只要面额设置的足够科学，贪心是对的。这可以说明，使用贪心的条件是很苛刻严格的，要经过严格的数学证明，才能够确定根据局部最优所得的结果对不对。
  2. 【贪心vs动态规划】但对于动态规划。它在哪种面额下都是可以的，这可以说明，动态规划(dp)的条件相比于贪心是更不苛刻的，正是因为贪心更严格，所以贪心的效率更高
  3. 【动态规划vs暴力】从上面可以看到，动态规划没有重复计算、也减去了没有必要的计算内容。减去不必要的计算任务，我们叫剪枝。也就是说动态规划自带剪枝，这是动态规划优于暴力的地方。

看到这里，相信你对DP有初步的了解。如果对自己没有信心，不要立刻看DP的严格定义。继续看一些例子，加深对它的感性认识。直到你对它有所感悟的时候，而且感悟到达极点的时候，再去看别人的总结，会恍然大悟，瞬间打通所有。

外卖小哥在一段时间内赚最多的钱（一维dp）

链接：动态规划 (第1讲)

题目：外卖小哥想在11个小时内赚最多的钱

  1. 横条前的数字：第i个外卖单子，一共有8个单子
  2. 横条的长度：做该单需要花费的时间段
  3. 横条上的红色数字：完成该单的报酬
    动态规划 - 图15

【思路】选与不选
【抽象问题】OPT[i]：完成前i项单子，赚的最多的钱

  1. OPT[1]：完成前1项单子，最多能赚5块（完成第一单）
  2. OPT[2]：完成前2项单子，最多能赚5块（只做第一单）
  3. OPT[3]：完成前3项单子，最多能赚8快（只做第三单）
  4. OPT[4]：完成前4项单子，最多能赚8块（只做第三单）
  5. OPT[8]：怎么算？

【OPT[8]】完成前8项单子赚的最多的钱，那就有两种可能：对于第8项单子，我是做，还是不做

  1. 做第8个单子：然后8-11的时间段就不能做别的了，所以只能做8之前的单子，这里记做pre[8]
  2. 不做第8个单子：那就是OPT[7]

然后在两种情况下找到最大值，即是OPT[8]，于是有以下公式：
动态规划 - 图16

【pre[]】pre数组怎么求呢？根据每个单子的结束时间来确定

【最终答案】
动态规划 - 图17

选出一组不相邻的数字且和最大（一维dp）

链接：动态规划第二讲第一题

题目：在一个数组arr中，找出一组不相邻的数字，使得最后的和最大
动态规划 - 图18

#include<stdio.h>
int max(int a, int b) {
    return a>b?a:b;
}

int dp_1(int arr[], int n) { //非递归
    int opt[105];
    int i;
    //初态
    opt[0]=arr[0];
    opt[1]=max(arr[0], arr[1]);
    //通式（选、不选中的最大值）：opt[i] = max{ opt[i-1], arr[i]+opt[i-2] }
    for (i=2; i<n; ++i) {
        opt[i] = max( opt[i-1], arr[i]+opt[i-2] );

        printf("opt[%d]=%d\n", i, opt[i]);
    }

    return opt[n-1];
}

int opt[105] = {0}; //保存记录
int dp_2(int arr[], int n) { //递归
    int i=n-1; //arr从0开始存储

    if (opt[i]!=0) return opt[i]; //计算过了

    if (i==0) {
        opt[i]=arr[0];
        return opt[i];
    } else if (i==1) {
        opt[i]=max(arr[0], arr[1]);
        return opt[i];
    } else {
        if (opt[i-1]==0) opt[i-1] = dp_2(arr, n-1);
        if (opt[i-2]==0) opt[i-2] = dp_2(arr, n-2);

        opt[i] = max( opt[i-1], arr[i]+opt[i-2] );
        printf("opt[%d]=%d\n", i, opt[i]);
        return opt[i];
    }
}

int main() {
    int arr[105] = {1, 2, 4, 1, 7, 8, 3};
    printf("%d", dp_2(arr, 7) ); //前7个数字
    return 0;
}

[总结] DP的解题经验

原文链接：告别动态规划，DP连刷 40 道题，我总结出了这些套路！这应该是把动态规划讲的最后的文章了

【步骤一】确定数组

  1. 梳理问题的条件
  2. 确定数组维度：一般影响因子有几个，数组就有几个维度
  3. 准确定义数组的含义

【步骤二】找出数组元素之间的关系

  1. 从末态找
  2. 分析问题的过程

【步骤三】找出初始值，即出口（从初态找）

  • 找初始值容易出错，有时候容易找的不完整，所以不能仅局限于在数组元素中下标>=0的程度，要多考虑几位

【注意】

  1. 下标问题：下标一般存1-n，0可以作为边界检查、也不容易搞乱

能不能凑出正整数s（二维dp）

链接：动态规划第二讲第二题

【题目】给定一个正整数s, 判断一个数组arr中，是否有一组数字加起来等于s
动态规划 - 图19

【第一步】确定数组

  1. 确定问题：①选数字；②数字和等于S；③问题：能不能选出这么一组数字
  2. 数组维数：影响因子是①数字之和、②单个数字 —> 二维dp
  3. 定义数组含义（即问题）：Subset[k][s]：从前k个元素中选一组数字，它们的和是s，subset[k][s]等于1表示能选出来

【第二步】确定元素间的关系
从后往前，当前数字是选还是不选，只要其中一个能凑出，就返回true
动态规划 - 图20
【第三步】找初始值，也就是出口

  1. s==0：空集就好了，这时候返回true
  2. k==0：只有0可以选了，如果这时候第0个数值刚好是s，则返回true，否则返回false

【代码】

#include<stdio.h>
#include<string.h>

// 从arr[]中的前k个元素中，选择一组元素，它们的和刚好等于s，则返回1
int dp[105][105]; //数组
int dp_rec(int arr[], int k, int s) { //递归
    int val1, val2;

    if (dp[k][s]!=-1) return dp[k][s]; //有历史记录，直接返回

    // 递归出口
    if (s==0) 
        dp[k][s]=0;
    else if (k==0) 
        dp[k][s] = arr[0]==s;

    // 通式
    else if (arr[k]>s) //选了第k个就超出了s，那不选
        dp[k][s] = dp_rec(arr, k-1, s);    
    else {
        val1 = dp_rec(arr, k-1, s); //不选
        val2 = dp_rec(arr, k-1, s-arr[k]); //选第k个
        dp[k][s] =  val1 || val2;
    }

    printf("dp[%d][%d]=%d\n", k, s, dp[k][s]);
    return dp[k][s];
}

int main() {
    int i,j;
    // 测试
    int n=6;
    int s=9;
    int arr[6] = {3, 34, 4, 12, 5, 2}; //0到n-1

    memset(dp, -1, sizeof(dp));
    printf("\n可以凑到吗？ %d\n", dp_rec(arr, n-1, s) );

    for (i=0; i<n; i++) {
        for (j=0; j<n; j++)
            printf("%d\t", dp[i][j]);
        printf("\n");
    }
    return 0;
}

01背包问题（二维dp）

视频链接：01背包问题
链接：01背包在线计算器

【题目】有n个物品及它们的重量和价格，问小偷的背包只能装下20kg，怎么装偷的最多？
动态规划 - 图21
【步骤1】确定数组

  1. 确定问题：①选物品；②物品的总重量≤W；③问题：求物品的总价值最大
  2. 数组维数：影响因子是①物品的总重量、②单个物品的重量 —> 二维dp
  3. 定义数组含义（即问题）：B[k][w]：在前k个商品中选取一组商品，重量≤w，物品总价值最大为B[k][w]

【步骤2】找出数组元素的关系
动态规划 - 图22

【步骤3】找初始值

B[0][0]->B[0][w]（第一行）都为0：没有物品时，最大价值为0
B[0][0]->B[k][0]（第一列）都为0：有物品，没有包来装，最大价值也是0

B(k,w)数组的值：
动态规划 - 图23
【代码】

#define N 5   //5个商品
#define W 20  //背包重量
int B[N+1][W] = {0};
int w[N+1] = {0, 2,3,4,5,9}; //从1-N开始记录
int v[N+1] = {0, 3,4,5,8,10}; //从1-N开始记录
void Knapsack(int B[N+1][], int w[], int v[]) {
    int i,j;
    int val1, val2;
    // 初始值（其实不用赋予初始值，B[][]数组定义时初始值即为0）
    for (j=0; j<=W; ++j) B[0][j]=0; //第一行
    for (i=0; i<=N; ++i) B[i][0]=0; //第一列
    // 递推
    for (i=1; i<=N; ++i) { //考虑前k个物品
        for (j=1; j<=W; ++j) { //背包的重量
            if ( w[i] > j ) { //第i件物品太重，背包已经装不下了
                B[i][j] = B[i-1][j]; //不考虑第i件
            } else {
                val1 = B[i-1][j];    //不选第i件
                val2 = B[i-1][j-w[i]]+v[i]; //选第i件
                B[i][j] = val1>val2 ? val1 : val2;
            }
        }
    }
}

dp有哪些类型

dp有哪些种类