[题目][蓝桥杯ALGO-22] 数的划分

一、题目

1、问题描述

将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。

例如:n=7,k=3,下面三种分法被认为是相同的。

1,1,5; 1,5,1; 5,1,1;

问有多少种不同的分法。

2、输入格式

两个正整数 n, k

3、输出格式

一个正整数,即不同的分法。

4、样例输入

7 3

5、样例输出

4 {四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;}

6、数据规模

6<n<=200,2<=k<=6

 

二、分析与思路

令 f[i][j] 表示 “数 i 被划分成 j 份的分法”,6 < i <= 200, 2 <= j <= 6,求解目标为 f[n][k]。

对于整数 i,如果需要划分为 j 份,首先每一份的值必然不为 0,故恒有 j <= i,即每份的最小值为 1,剩下的值为 i - j,而这个 i - j 我们可以全部放到 j 份中的任意一份,对应的是 f[i - j][1](将数 i - j 划分成 1 份)也可以是其中 2, 3, ...(f[i - j][2, 3...])份,这时候我们已经构建出了一个递推关系,也就可以开始求状态转移方程了。

依上述关系,可得:

f[i][j] = f[i - j][1] + f[i - j][2] + ... f[i - j][j] ①

又 f[i - 1][j - 1] = f[i - j][1] + f[i - j][2] + ... + f[i - j][j - 1] ②,将 ② 式代入 ① 式,可得:

f[i][j] = f[i - j][j] + f[i - 1][j - 1] ,即状态转移方程。

尽管是道很简单的动态规划,但后面 ③ 式的简化我觉得没那么容易想到。如果直接使用 ① 式,时间复杂度为 O(n * k * k),尽管这道题数据量小,是吃得消的,但一旦上调则难以通过。③ 式通过简单的数列知识对式子简化,时间复杂度也随之下降至 O(n * k)。

 

三、代码

 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n, k, f[205][7];
 5 
 6 int main() {
 7     cin >> n >> k;
 8     for (int i = 1; i <= n; i++) {
 9         f[i][1] = 1;
10         for (int j = 2; j <= min(i, k); j++)
11             f[i][j] = f[i - j][j] + f[i - 1][j - 1];
12     }
13     cout << f[n][k];
14     return 0;
15 }

 

 

 

四、相关知识点

4.1  记忆化搜索与动态规划

上一篇:ubuntu重装系统记录


下一篇:D. Prefixes and Suffixes 解析(思維、字串、Z-Algo)