C语言网(Dotcpp.com)奉行“学练同步，知行合一”的学习理念，希望大家都能理论与动手一起加强！拒绝理论派！
每月月赛，最后一个周六晚八点开始，请提前预约参赛，参与排名！
混一天和努力一天，一天看不出任何差别，三天看不到任何变化，七天也看不到任何距离……
但是一个月后会看到话题不同，三个月后会看到气场不同，半年后会看到距离不同，一年后会看到人生道路截然不同。
请坚信你所喜爱的事物！
举办比赛权限已经完全开放，支持老师、个人随时抽题创建校内赛等比赛，达到P2级即可
因比赛为公共资源，比赛名称建议包含学校/组织名称具有辨识度，比赛名称、公告不文雅、灌水将被删除比赛并取消权限！
世界上有10种人，一种是懂二进制的，另一种是不懂二进制的~
题库的题不仅仅支持C语言C++、java，Python和php也可以提交
编程小组功能上线！欢迎各位老师、社团协会小组负责人申请创建，方便教学、训练！
学习交流 QQ1群156740915、4群 364137421、 211300176、博主群487133400 Python小组群 783851273 验证信息备注网站昵称！

列公子

用户名：lielielie

访问量：6851

签　名：

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

　　自我简介：

TA的其他文章

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

蓝桥杯算法训练VIP-水仙花-题解(C++代码)
浏览：111

蓝桥杯 FBI树 DFS
浏览：214

你可能喜欢

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

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

优质题解

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

　　作者: 列公子　　　　发表时间：2020-02-24 15:36:19 浏览：1156　|　评论：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分

13 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

　　评论区

綮世

这个记忆化搜索本质上不还是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语言程序设计教程（第三版）课后习题3.7 （C语言代码）

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

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

明明的随机数（C++代码）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

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

评论区

精彩推荐

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

破解简单密码（C语言代码）

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

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

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

C语言训练-素数问题（C语言代码）

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

P1001 （C语言代码）

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

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

列公子

TA的其他文章

你可能喜欢

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

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

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

明明的随机数 （C++代码）

【绝对值排序】 （C++代码）（利用两个库函数——abs()求绝对值 和 sort()快排）

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

评论区

精彩推荐

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

破解简单密码 （C语言代码）

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

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

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

C语言训练-素数问题 （C语言代码）

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

P1001 （C语言代码）

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

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

明明的随机数（C++代码）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

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

　　评论区

破解简单密码（C语言代码）

C语言训练-素数问题（C语言代码）