1531题 - 数的划分盒子放球模型(记忆化搜索 / 动态规划) 、完全背包(动态规划) 三种方法汇总

1988 阅读 13 评论 0 点赞

原题链接：蓝桥杯算法提高VIP-数的划分

#  数的划分  动态规划 / 递归记忆化搜索

## 1.  类似完全背包的动态规划解法

有 N 个整数(1 ~ N)，每个整数可以使用多次, 使得其总和等于 N

### 1.1 最优值定义和递归关系

定义 $$dp[i][j]$$ 为 **只用不大于** $$i$$ 的整数 凑出 $$j$$ 的**最大方案数** (最优值)

$$dp[i][j] =  dp[i-1][j] + dp[i][j - 1], i \le j$$

$$dp[i][j] = dp[i-1][j], i > j$$

第一行的公式前后两部分 分别对应 **不使用数字 i** 和 **使用数字 i**，当 $$i > j$$ 时使用数字 i 也无意义

### 1.2 边界值
$$dp[1][j] = 0 , 0 \le j \le N$$

### 1.3 完整代码 (AC)
````cpp
#include <cstdio>
const int maxn = 110;
int N;
int dp[maxn][maxn];     // dp[i][j] 表示 只用 小于等于i的数字 凑出j 的方案数

int solve(){
    for (int i = 0; i <= N; i++)
        dp[1][i] = 1;

for (int i = 2; i <= N; i++){
        for (int j = 0; j <= N; j++){
            dp[i][j] = dp[i-1][j];  // 不用 i
            if (i <= j)     // 用 i, 前提是 i<=j, 否则没意义
                dp[i][j] += dp[i][j-i];
        }
    }
    return dp[N][N];
}

int main(){
    scanf("%d", &N);
    printf("%d", solve());
    return 0;
}
```

### 1.4 完整代码 (AC)  滚动数组优化内存
```cpp
#include <cstdio>
const int maxn = 110;
int N;
int dp[2][maxn];     // dp[i][j] 表示 只用 小于等于i的数字 凑出j 的方案数

int solve(){
    int p = 0;
    for (int i = 0; i <= N; i++)
        dp[p][i] = 1;

for (int i = 2; i <= N; i++){
        p = 1 - p;
        for (int j = 0; j <= N; j++){
            dp[p][j] = dp[1 - p][j];           // 不用 i

if (i <= j)           // 用 i, 前提是 i<=j, 否则没意义
                dp[p][j] += dp[p][j - i];
        }
    }
    return dp[p][N];
}

int main(){
    scanf("%d", &N);
    printf("%d", solve());
    return 0;
}
```

## 2. 盒子放球模型, 分别以记忆化搜索和动态规划实现

将 $$n$$ 个 球放在 $$k$$ 个盒子 $$(1 \le k \le n)$$里，每个盒子不空，共有多少种方案

### 2.1 定义及递归关系

定义 $$dp[n][k]$$ 为 将 $$n$$ 个球 放在 $$k$$ 个盒子里，每个盒子不空的方案数

$$dp[n][k] = dp[n-k][k] + dp[n-1][k-1]$$

加号左右分别对应以下两种情况：
- **每个盒子**里都**至少有两个球**, 则等价于：先在每个盒子里放一个球（只有一种方案），再将 ```n-k```个球放进 ```k``` 个箱子

- 至少有一个盒子里**只有一个球**, 排除这一个盒子（和这一个球）后，问题为 将 ```n-1``` 个球放进 ```k-1``` 个箱子

### 2.2 边界值

$$ dp[n][1] = dp[n][n] = 1, 1 \le n \le N $$

### 2.3 记忆化搜索

```cpp
#include <cstdio>
const int maxn = 110;

int book[maxn][maxn];

int solve(int n, int k){    // 记忆化搜索, n个球, 分成k组, 每组不空, 有多少种方案
    if (book[n][k])     // 已有结果
        return book[n][k];
    if (n < k)      // 分成的组数比球数多
        return 0;
    if (k == 1 || n == k)   // 都放在一个盒子 或 每个盒子都放一个
        return 1;
    // 每个盒子至少有两个球 + 至少有一个盒子里只有一个球
    book[n][k] = solve(n - k, k) + solve(n - 1, k - 1);
    return book[n][k];
}

int main(){
    int N;
    scanf("%d", &N);

int ans = 0;
    for (int i = 1; i <= N; i++)
        ans += solve(N, i);

printf("%d\n", ans);
    return 0;
}
```

### 2.4 动态规划

```cpp
#include <cstdio>
#include <cstring>
const int maxn = 110;

int dp[maxn][maxn];     // dp[i][j] 为 i 个球 放进 k个盒子, 每个盒子不空, 有多少方案

int solve(int N){      // 动态规划
    memset(dp, 0, sizeof(dp));

for (int i = 1; i <= N; i++)    // 全放一个盒子里 或 每个盒子都放一个
        dp[i][1] = dp[i][i] = 1;

for (int i = 3; i <= N; i++){   // 2 个球的情况在上面的循环已解决
        for (int j = 2; j < i; j++){    // 盒子数大于球数无解
            dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];
        }
    }
    int total = 0;
    for (int k = 1; k <= N; k++)
        total += dp[N][k];
    return total;
}

int main(){
    int N;
    scanf("%d", &N);
    printf("%d", solve(N));
    return 0;
}
```

0.0分

12 人评分

本文分类：题解列表
浏览次数：1988 次浏览
发布日期：2020-02-24 15:36:19
本文链接：https://blog.dotcpp.com/a/66905

上一篇 > [编程入门]矩阵对角线求和-题解(C语言代码)
下一篇 > 弟弟的作业（Python代码）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 13 条评论

勾逼o 9月前回复TA

@oh 作者那个地方打错了，但代码还是对的。是j-i不是j-1。dp[3][5]要用3来凑5的情况等于凑出2的情况，因为凑出2的这些每个情况再来个数字3就成了凑出5且用到了3的情况。因为dp[3][5]中没有数超过3，所以凑出2的数字也不能超过3，即为dp[i][j-i]

綮世 2年前回复TA

这个记忆化搜索本质上不还是DP吗？

一个人的巴黎 2年前回复TA

【每个盒子里都至少有两个球, 则等价于】这里错了，应该是每个盒子里至少有一个吧，至少有2个，不应该减去2k吗

江鱼儿 4年前回复TA

@Cunese 另外一个dp[i-1][j]的意思是之前没用i的时候的次数（意思是这次这个i我不用）

江鱼儿 4年前回复TA

@Cunese 意思就是之前用i来凑j-i时的次数再加上这次的i正好就等于j了

Cunese 4年前回复TA

看不懂为什么j-i

Cunese 4年前回复TA

@oh 看不懂为什么j-i

列公子 4年前回复TA

@oh 法1 加了用滚动数组优化内存, 可以看看

列公子 4年前回复TA

@oh 解决了吗？

oh 4年前回复TA

我知道了，是j-i不是j-1

1531题 - 数的划分 盒子放球模型(记忆化搜索 / 动态规划) 、完全背包(动态规划) 三种方法汇总

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 13 条评论

发表评论 取消回复

1531题 - 数的划分盒子放球模型(记忆化搜索 / 动态规划) 、完全背包(动态规划) 三种方法汇总

评论列表共有 13 条评论

发表评论取消回复