列公子

用户名：lielielie

访问量：8859

签　名：

等　　级
排　　名	1615
经　　验	2513
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯摆动序列 DFS -
浏览：382

蓝桥杯金陵十三钗 DFS + 剪枝
浏览：251

蓝桥杯 3000米排名预测 - DFS/全排列
浏览：222

你可能喜欢

A+B for Input-Output Practice （C++代码）

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

　　作者: 列公子　　　　发表时间：2020-02-24 15:36:19 浏览：1581　|　评论：7　

原题链接：蓝桥杯算法提高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分

14 人评分

C语言网强势推出「真C语言」普惠学习计划，依托C语言网强大的技术与丰富的资源支撑，让你一次性学会C语言从此告别“假C语言”，“只会理论”，“写不出代码”等问题，以含金量和学习效果勇敢挑战同类辅导！点击学习

　　评论区

綮世

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

2022-07-29 10:36:34

一个人的巴黎

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

2022-02-15 11:12:30

Cunese

看不懂为什么j-i

2020-09-20 19:08:05

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

2020-03-24 16:45:12

我把每步的过程输出来，结果是这样的
dp[2][3]+=dp[2][2]=(1+2)=2；
dp[2][5]+=dp[2][4]=(1+3)=3；
dp[3][3]+=dp[3][2]=(2+2)=3；
dp[3][4]+=dp[3][3]=(3+3)=4；
dp[3][5]+=dp[3][4]=(3+4)=5；
dp[4][4]+=dp[4][3]=(4+3)=5；
dp[4][5]+=dp[4][4]=(5+5)=6；
dp[5][5]+=dp[5][4]=(6+5)=7；
这咋算的啊，见鬼

2020-03-24 15:28:33

太诡异了，我的天，这怎么算的啊（方法一）

2020-03-24 15:24:30

第一种方法感觉dp[i][j]的含义不正确啊，dp[3][5]=5;          dp[2][5]=3;           dp[3][4]=4;         
dp[3][5]!=dp[2][5]+dp[3][4]啊

2020-03-24 15:03:55

列公子

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

A+B for Input-Output Practice （C++代码）

C语言训练-排序问题<1> （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

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

评论区

精彩推荐

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

【绝对值排序】（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

【明明的随机数】（C语言代码）

Hello, world! （C语言代码）

1071题解

列公子

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

A+B for Input-Output Practice （C++代码）

C语言训练-排序问题<1> （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

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

评论区

精彩推荐

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

【绝对值排序】 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

【明明的随机数】 （C语言代码）

Hello, world! （C语言代码）

1071题解

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

　　评论区

C二级辅导-进制转换（C语言代码）

【绝对值排序】（C++代码）

【明明的随机数】（C语言代码）