Keshawn_lu's Blog

牛客网 KY8.整数拆分

字数统计: 415阅读时长: 1 min
2021/03/03 Share

题目简介:

一个整数总可以拆分为2的幂的和,例如: 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。 再比如:4可以拆分成:4 = 4,4 = 1 + 1 + 1 + 1,4 = 2 + 2,4=1+1+2。 用f(n)表示n的不同拆分的种数,例如f(7)=6. 要求编写程序,读入n(不超过1000000),输出f(n)%1000000000。

输入描述:

1
每组输入包括一个整数:N(1<=N<=1000000)。

输出描述:

1
对于每组数据,输出f(n)%1000000000。

输入

1
7

输出

1
6

思路:

动态规划,dp[i]代表数字i的拆分方法的数量。

对于奇数,我们可以将其拆分为 偶数+1 的形式,由于1无法再拆分,所以dp[i] = dp[i - 1]

对于偶数,如4,我们可以将其拆分为2 + 1 + 12 + 2的形式,所以dp[i] = dp[i - 2] + dp[i / 2]

特别想说明的是,对于偶数来说,若拆分的情况里没有1的存在,那么其余数字必定都可以/ 2,所以可以相当于dp[i / 2]

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>

using namespace std;


int main()
{
int n;
cin >> n;

vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;

for (int i = 3; i <= n; i++) {

if (i % 2 == 0)
dp[i] = dp[i - 2] + dp[i / 2];
else
dp[i] = dp[i - 1];

dp[i] = dp[i] % 1000000000;
}

cout << dp[n] << endl;
}
CATALOG
  1. 1. 题目简介:
  2. 2. 输入描述:
  3. 3. 输出描述:
  4. 4. 输入
  5. 5. 输出
  6. 6. 思路:
  7. 7. 代码如下: