算法之动态规划篇

Lili Liang 梁莉莉

算法之动态规划篇

Apr 12, 2020 ｜ # 算法

1 dp基本性质
2 装箱问题
3 开心的金明(0/1背包)
4 数的划分(分类讨论，dfs实现）
5 摆动序列(dfs实现）
6 传球游戏(环形dp)
7 方格取数(多线程dp）
8 K好数

1 dp基本性质

最优子结构
- 当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。
- 在动态规划算法中，利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
重叠子问题
- 子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用。对每个子问题只解一次，而后将其保存在一个表格中，当再次需要的时候，只是简单的用常数时间查看一下结果。
无后效性
- 即某阶段状态一旦确定，就不受这个状态以后决策的影响。即某状态以后的过程不会影响以前的状态，只与当前状态有关。

2 装箱问题

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T83

题目大意：

有一个箱子容量为 V（正整数，0 ＜＝ V ＜＝ 20000），同时有 n 个物品（0 ＜ n ＜＝ 30），每个物品有一个体积（正整数）。
要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

解题思路：

最经典的 $$dp$$ 问题，直接上手

$$dp[j]$$ ：当体积为 $$j$$ 时，最大填充为 $$dp[j]$$
$$dp$$ 方程：

dp[j] = max(dp[j], dp[\, j - w[i] \,] + w[i])

题解：

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 20010;
//dp[j]：当体积为j时，最大填充为dp[j] 
int dp[maxn], w[35];

int main(){
    // freopen("input.txt", "r", stdin);
    int v, n;
    cin >> v >> n;
    for(int i = 0;i < n;i++){
        cin >> w[i];
    }
    //n个物品 
    for(int i = 0;i < n;i++){
        //总体积为v 
        for(int j = v;j >= w[i];j--){
            dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
        }
    }
    printf("%d\n", v - dp[v]);
    return 0;
}
/*
24
6
8
3
12
7
9
7

0
*/

3 开心的金明(0/1背包)

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T93

题目大意：

在不超过 $$N$$ 元（可以等于 $$N$$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

解题思路：

约定， $$dp[i][j]$$ 表示判定了 $$i$$ 件物品，剩余钱数为 $$j$$ 时，每件物品的价格与重要度的乘积的总和最大。

典型的 $$0/1$$ 背包问题
$$dp$$ 方程：
$dp[i][j] = max( dp[i - 1][j], \,dp[i - 1][j - v] + v * p)$
其中， $$v$$ 表示物品的价格， $$p$$ 表示该物品的重要度。

题解：

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 30005;
//dp[i][j]表示判定了i件物品，剩余钱数为j时，每件物品的价格与重要度的乘积的总和最大
int dp[30][maxn] = {0};

int main(){
    int n, m;
    cin >> n >> m;
    //物品件数
    for(int i = 1;i <= m;i++){
        int v, p;
        cin >> v >> p;
        //总钱数
        for(int j = 1;j <= n;j++){
            if(j >= v){
                dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - v] + v * p);
            }else{
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    printf("%d\n", dp[m][n]);
    return 0;
}
/*
1000 5
800 2
400 5
300 5
400 3
200 2

3900
*/

4 数的划分(分类讨论，dfs实现）

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T84

题目大意：

将整数 n 分成 k 份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n = 7，k = 3，下面三种分法被认为是相同的。
1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。

解题思路：

考虑四种情况：

至少存在一个 $$1$$ 的情况：总数 $$- 1$$ ，个数 $$- 1$$
不存在 $$1$$ 的情况：每个数分别 $$-1$$ ，则总数 $$-(k*1)$$ ，个数不变
当 $$n=k$$ 或 $$k=1$$ 时，只能有 $$1$$ 种划分方法，边界条件，返回 $$1$$
另外当 $$n<k$$ 时，无法划分，此时返回 $$0$$

题解：

#include <iostream>
#include <cstdio>
using namespace std;

int dfs(int n, int k){
    if(n == k || k == 1){
        return 1;
    } 
    if(n < k){
        return 0;
    }
    //至少存在一个1的情况：总数 - 1， 个数 - 1
    //一定不存在1的情况： k个数均≥2，则每个数都 - 1，总数 - k * 1，个数不变 
    return dfs(n - 1, k - 1) + dfs(n - k, k);
}

int main(){
    int n, k;
    cin >> n >> k;
    printf("%d\n", dfs(n, k));
    return 0;
}
/*
7 3

4
*/

5 摆动序列(dfs实现）

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T44

题目大意：

如果一个序列满足下面的性质，我们就将它称为摆动序列：

序列中的所有数都是不大于k的正整数；

序列中至少有两个数；

序列中的数两两不相等；

如果第 i – 1 个数比第 i – 2 个数大，则第 i 个数比第 i – 2 个数小；如果第 i – 1 个数比第 i – 2 个数小，则第 i 个数比第 i – 2 个数大。

比如，当 k = 3 时，有下面几个这样的序列：
1 2
1 3
2 1
2 1 3
2 3
2 3 1
3 1
3 2
一共有 8 种，给定 k ，请求出满足上面要求的序列的个数。

解题思路：

本题用 $$dfs$$ 实现，其中条件 $$1$$ 与条件 $$2$$ 很容易满足。
条件 $$3$$ 与条件 $$4$$ ，用下列方程即可满足： $$$ (arr[x - 2] - arr[x - 3]) * (arr[x - 1] - arr[x - 3]) < 0 $$$

题解：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 30;
int arr[maxn], vis[maxn];
int ans = 0, n;

void dfs(int x){
    if(x > 1){
        if(x == 2){
            ans++;
        //公式满足条件3与条件4 
        }else if( (arr[x - 2] - arr[x - 3]) * (arr[x - 1] - arr[x - 3]) < 0){
            ans++;
        }else{
            return;
        }
    }
    for(int i = 1;i <= n;i++){
        if(!vis[i]){
            vis[i] = 1;
            arr[x] = i;
            dfs(x + 1);
            vis[i] = 0;
        }
    }
}

int main(){
    memset(vis, 0, sizeof(vis));
    cin >> n;
    dfs(0);
    printf("%d", ans);
    return 0;
}
/*
3

8
*/

6 传球游戏(环形dp)

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T97

题目大意：

有 $$n$$ 个同学围成一圈，小蛮传了 $$m$$ 次球后，球又回到自己手中，问有多少种传球方法？

解题思路：

约定， $$dp[i][j]$$ 表示传了 $$i$$ 次球，到第 $$j$$ 个人手上的传球方法。

因为是环形传球，因此需要考虑两个边界，第 $$1$$ 个人和第 $$n$$ 个人的情况。
当前同学的传球次数，为左右同学(传了 $$i-1$$ 次球)的传球方法相加 $$$ dp[i][j] = dp[i - 1][x] + dp[i - 1][y] $$$ 其中 $$x=j-1,y=j+1$$

题解：

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 40;
//dp[i][j]表示传了i次球，到第j个人的次数 
int dp[maxn][maxn] = {0};

int main(){
    int n, m;
    cin >> n >> m;
    //传了0次球，到第一个人的次数，自然为1 
    dp[0][1] = 1;
    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= n;j++){
            int x = j - 1, y = j + 1;
            //考虑第1个人的情况 
            if(j == 1){
                x = n;
            }
            //考虑第n个人的情况
            if(j == n){
                y = 1;
            }
            //当前的情况等于左右传了i - 1次球的情况相加 
            dp[i][j] = dp[i - 1][x] + dp[i - 1][y];
        }
    }
    printf("%d\n", dp[m][1]);
    return 0;
}
/*
3 3

2
*/

7 方格取数(多线程dp）

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T79

题目大意：

设有 N * N 的方格图(N <= 10)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。
某人从图的左上角的 A 点(1, 1)出发，可以向下行走，也可以向右走，直到到达右下角的 B 点(N, N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0 ）。
此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。

解题思路：

可模拟两个人同时从 $$(1,1)$$ 走到 $$(N,N)$$
$$dp$$ 方程：

$$dp[x1][x2][y1][y2] = max(dp[x1 - 1][y1][x2 - 1][y2], $$

$$ dp[x1][y1 - 1][x2][y2 - 1], $$

$$dp[x1 - 1][y1][x2][y2 - 1], $$

$$dp[x1][y1 - 1][x2 - 1][y2]) $$

考虑两人走到同一点的特殊情况，只能加一次权值。

题解：

/*
模拟两个人同时从(1,1)走到(N,N)，
转移方程:dp[x1][x2][y1][y2] = max(dp[x1 - 1][y1][x2 - 1][y2], 
                                 dp[x1][y1 - 1][x2][y2 - 1], 
                                 dp[x1 - 1][y1][x2][y2 - 1], 
                                 dp[x1][y1 - 1][x2 - 1][y2]) 
考虑两人走到同一点的特殊情况，只能加一次权值。 
*/
#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 20;
int g[maxn][maxn] = {0}, dp[maxn][maxn][maxn][maxn] = {0};

int main() {
    // freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    while(true){
        int x, y, value;
        cin >> x >> y >> value;
        if(x == 0 && y == 0 && value == 0){
            break;
        }
        g[x][y] = value;
    }
    for(int x1 = 1;x1 <= n;x1++){
        for(int y1 = 1;y1 <= n;y1++){
            for(int x2 = 1;x2 <= n;x2++){
                for(int y2 = 1;y2 <= n;y2++){
                    int temp = max(dp[x1 - 1][y1][x2 - 1][y2], dp[x1][y1 - 1][x2][y2 - 1]);
                    temp = max(temp, dp[x1 - 1][y1][x2][y2 - 1]);
                    temp = max(temp, dp[x1][y1 - 1][x2 - 1][y2]);
                    if(x1 == x2 && y1 == y2){
                        dp[x1][y1][x2][y2] = temp + g[x1][y1];
                    }else{
                        dp[x1][y1][x2][y2] = temp + g[x1][y1] + g[x2][y2];
                    }
                }
            }
        }
    }
    printf("%d\n", dp[n][n][n][n]);
    return 0;
}
/*
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

67
*/

8 K好数

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T13

题目大意：

$$K$$ 好数定义：一个自然数 $$N$$ 的 $$K$$ 进制表示中任意的相邻的两位都不是相邻的数字。求 $$L$$ 位 $$K$$ 进制数中 $$K$$ 好数的数目。输出它对 $$1000000007$$ 取模后的值。

解题思路：

我们约定， $$dp[i][j]$$ 表示长度为 $$i$$ ，以 $$j$$ 开头的 $$K$$ 好数个数。

$$K$$ 好数中除开头外，每位数的取值为： $0 \sim K-1$ ；
以 $$K=3，L=3$$ 为例：

$$$ans = dp[3][0]+dp[3][1]+dp[3][2]$$$
其中 $$dp[3][0]=dp[2][0]+dp[2][2]$$
$$dp[3][1]=dp[2][1]$$
$$dp[3][2]=dp[2][2]+dp[2][0]$$
以此类推长度为 $$2$$ ，长度为 $$1$$ 的情况；
因此可推出 $$dp$$ 方程：

$$$dp[i][j]=dp[i][j]+dp[i-1][x]$$$
其中 $$x$$ 取值为 $0 \sim K-1$
另外要注意， $$K$$ 好数开头不能为 $$0$$ ；

题解：

#include <iostream>
#include <cstdio>
using namespace std;

#define MOD 1000000007

const int maxn = 105;
//dp[i][j]表示长度为i，以j开头的K好数个数 
int dp[maxn][maxn];

int main(){
    int k, l;
    cin >> k >> l;
    //dp[1][i]表示长度为1，以i开头的K好数个数，此时个数均为 1 
    for(int i = 0;i < k;i++){
        dp[1][i] = 1;
    }
    //长度由2 → l 
    for(int i = 2;i <= l;i++){
        //表示以j开头的个数，因为是K进制，所以K的范围为0 ~ K - 1 
        for(int j = 0;j < k;j++){
            //枚举以j为开头时的所有情况 
            for(int x = 0;x < k;x++){
                //符号K好数要求的数 
                if(x != j + 1 && x != j - 1){
                    //dp方程 
                    dp[i][j] += dp[i - 1][x];
                    //注意取模 
                    dp[i][j] %= MOD;
                }
            }
        }
    } 
    int ans = 0;
    //开头不能为O,所以开头i的范围为1 ~ K - 1 
    for(int i = 1;i < k;i++){
        ans += dp[l][i];
        ans %= MOD;
    } 
    printf("%d\n", ans);
    return 0;
}
/*
4 2 

7
*/

Tags： / C/C++ / dp