DP: Dynamic Programming

概述

动态规划是为了避免递归中出现重复计算的一种策略.

对于子问题重叠的情况特别有效, 因为他将子问题解保存在表格中, 当需要某个子问题的解时,可以直接取值.

核心思想

将待求解问题分解为若干子问题, 子问题与子问题有重叠部分.

按顺序求解子问题, 前一子问题为后一子问题的求解提供了有效信息.

例如从n=1开始解决, 递推到n=N, 求出最终值.

1. 寻找最优子结构;
2. 列出递归方程, 自底向上对每个子结构解一次并保留到表中, 需要时在表中查找;
3. 找到最优解;

应用场景

问题可以分解为若干子问题并可以独立求解子问题.
子问题有重叠.

求解步骤

1. 分析最优解的性质, 并刻画其结构特征;
2. 定义最优解变量, 定义最优解公式;
3. 自低向上计算最优解;
4. 构造问题最优解;

示例1: 走楼梯

走楼梯: 每次走楼梯可以走1级或2级, 一共有多少种走法

解析: f(n) = f(n-1)+f(n-2)

int countStep(int n) {
    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    int res = 0;
    int a = 1;
    int b = 2;
    for (int i = 3; i <= n; i++) {
        res = a + b;
        a = b;
        b = res;
    }
    return res;
}

示例2: 机床切割

最优解: 假设5台机床, 每台由不同人来操作, 每台机器能操作的零件数量不一样. 工人总数为10. 每台机床的零件数和工人数:50(3),100(4),250(5),300(5),190(4). 求最大零件数.

解析: 当只考虑1台机床时, 找到最大零件数. 当2台机床的时候, 可以从机床1抽取人去第二台机床, 也可以不开第二台机床, 求出最大值.

P[i]表示第i台机床需要的工人数量, G[i]表示第i台机床零件数
F(i,j)表示第i台机床j个操作工人的最大零件数.
F(i,j)=max(F(i-1,j),F(i-1,j-P[i-1]+G[n-1]))

示例3: 男女排座位

座位问题: n个人坐成一排, 有男生和女生, 女生边上至少要有一个女生.

分析: dp[i][0]表示i个人的排座方式且最后一个为男生, dp[i][1]表示i个人的排座方式且最后一个为女生.

如果最后一个为男生: dp[i][0] = dp[i-1][0] + dp[i-1][1], 最后一个是男生,就无所谓前面是男生还是女生.
如果最后一个为女生: dp[i][1] = dp[i-2][0] + dp[i-1][1], 最后一个是女生倒数第二个就不能是男生, 但是dp[i-1][i]未包含倒数第2个前面是男生的情况.

int seats(int n) {
    vector<vector<int>> dp(n+1, vector<int>(2 ,0));
    dp[1][0] = 1;
    dp[2][0] = 1;
    dp[2][1] = 1;

    for (int i = 3;i <= n; i++) {
        dp[i][0] = dp[i-1][0] + dp[i-1][1];
        dp[i][1] = dp[i-2][0] + dp[i-1][1];
    }

    return dp[n][0] + dp[n][1];
}

示例4: 邮票求和

邮票问题: 判断若干邮票组合成特定值最少需要多少张, 邮票面值按升序排列. 如果5票邮票1,3,3,3,4组合7最少需要2张, 无解输出0.

解析: 先排第i张邮票, 假如不选中就是dp[num], 假如选中就是dp[num-vec[i]]+1.

int stamps(int num, vector<int> &vec) {
    int count = (int)vec.size();
    // 对应i值需要多少张邮票
    vector<int> dp(num+1, 1000);
    dp[0] = 0;
    for (int i = 0; i < count; i++) {
        for (int j = num; j >= vec[i] ; j--) {
            dp[j] = min(dp[j], dp[j-vec[i]] + 1);
        }

    }

    return dp[num];
}

示例5: 分水果

有若干不同重量水果, 将水果分成两份, 求分成两份后最小重量差值.

分析: 求出最接近总重量中间值的水果重量, 即可求出小份水果重量.

// 分水果问题
// 有若干重量不等水果, 划分为2份水果, 求两份水果最小差值
int fruit(vector<int> vec) {
    int num = 0;
    for(int i = 0;i < vec.size();i++) {
        num += vec[i];
    }
    // 计算出最接近总量中间值的重量即可求出差值
    int half = num / 2;
    // num / 2舍去部分小数, 所以num / 2 + 1
    vector<int> dp(num / 2 + 1, 0);

    for (int i = 0;i < vec.size(); i++) {
        for (int j = half; j >= vec[i]; j--) {
            // 不选取该水果为dp[j], 选取该水果为dp[j-vec[i]]+vec[i]
            dp[j] = max(dp[j], dp[j-vec[i]] + vec[i]);
        }
    }
    // 因为除以2舍去部分小数, dp[half]一定小于num - dp[half]
    return num - 2 * dp[half];
}

示例6: 两船装货

有两艘船和若干货物, 判断两船是否可以装完这些货物.

分析: 先尽量装满小船, 然后判断剩下货物是否可以装上大船.

bool boat(int a,int b, vector<int> vec) {
    int num = 0;
    for(int i = 0;i < vec.size();i++) {
           num += vec[i];
    }
    int c = a+ b;
    a = min(a, b);
    b = c - a;
    vector<int> dp(a+1, 0);

    for (int i = 0;i < vec.size(); i++) {
        for (int j = a; j >= vec[i]; j--) {
            dp[j] = max(dp[j], dp[j-vec[i]]+vec[i]);
        }
    }

    return num - dp[a] < b;
}

示例7: 安排工作

安排工作: 有一些工作, 每个工作有开始时间/结束时间/报酬, 一次只能完成一份工作, 如何安排工作可以获得最大报酬.

解析: 设置dp[i]为前i个工作能获得的最大报酬.
对于第i个项目, 前面第j个项目已满足条件.
如果做第i个项目: dp[i] = dp[j]+ jobs[i].value
如果不做第i个项目: dp[i] = dp[i-1]

int jobPlanCmp(vector<int> a, vector<int> b) {
    return a[0] < b[0];
}
// 项目安排
// 有多个项目可以做, 每个项目有开始时间/结束时间/报酬, 一次只能做一个项目, 如何获取最大报酬
// 解析: 根据时间规划最大报酬
int jobPlan(vector<vector<int>> &jobs) {
    int n = (int)jobs.size();
    // 按项目开始时间排序
    sort(jobs.begin(), jobs.end(), jobPlanCmp);

    vector<int> dp(n + 1, 0);
    // dp[i]表示前i个项目的最大报酬
    dp[1] = jobs[1][2];
    int j = 0;
    for(int i = 1;i <= n; i++) {
        for (j = i - 1; j >= 1; j--) {
            if (jobs[j-1][1] <= jobs[i-1][0]) {
                break;
            }
        }
        dp[i] = max(dp[j] + jobs[i-1][2], dp[i-1]);
    }

    return dp[n];
}

示例8: 导弹拦截

拦截导弹: 有一批高度不一样的导弹, 一次可以拦截多个导弹,拦截导弹的高度只能递减, 一次最多拦截多少导弹.

解析: dp[i]表示拦截第i颗导弹时, 最大可以拦截的导弹数.
如果拦截前i颗的导弹数就不知道前i颗导弹的具体高度是多少.

int missile(vector<int> vec) {
    int n = (int)vec.size();
    // 拦截第i个导弹最多拦截数
    vector<int> dp(n+1, 0);
    dp[1] = 1;
    int res = 1;
    for (int i = 2; i <= n; i++) {
        int ii = i - 1; // 当前导弹序号
        for (int jj = 0; jj < ii; jj++) {
            if (vec[jj] >= vec[ii] && dp[jj+1] >= dp[i]) {
                dp[i] = dp[jj+1] + 1;
                res = max(res, dp[i]);
            }
        }
    }
    return res;
}

示例9: 最大递增子序列

最大递增子序列, 给定一个数组, 输出最大递增子序列个数

解析: dp[i]表示包含第i个元素的子序列个数. 当前面第j个元素比当前元素小, 子序列个数加1.

int subSeriel(vector<int> vec) {
    int n = (int)vec.size();
    vector<int> dp(n+1, 1);
    
    dp[0] = 0;
    for (int i = 2; i <= n; i++) {
        int ii = i-1;
        for (int jj = 0;jj < ii;jj++) {
            int j = jj + 1;
            if (vec[ii] > vec[jj] && dp[j] >= dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    return dp[n];
}

示例10: 出入栈问题

给定一个数字, 表示操作次数, 最初和最后栈都为空. 输出一共有多少种操作序列.

解析: dp[i][j]表示进行i次入栈和j次出栈的操作总数.
如果i和j相等时, dp[i][j]=dp[i][j-1], 因为出栈数和入栈数总是相等, 最后一次必为入栈;
如果i和j不相等时, dp[i][j] = dp[i-1][j] + dp[i][j-1];
只入不出只有一种情况, dp[i][0] = 1;

int stack(int n) {
    if(n % 2 == 1) return 0;
    // i个操作的序列数
    vector<vector<int>> dp(n/2 + 1, vector<int>(n/2+1,0));
    for (int i = 0; i < n/2 + 1; i++) {
        dp[i][0] = 1;
    }

    for (int i = 1; i <= n / 2; i++) {
        for (int j = 1; j <= i; j++) {
            if (i == j) {
                dp[i][j] = dp[i][j-1];
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }

    return dp[n/2][n/2];
}