题目简介:
一个整数总可以拆分为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 + 1
或2 + 2
的形式,所以dp[i] = dp[i - 2] + dp[i / 2]
。
特别想说明的是,对于偶数来说,若拆分的情况里没有1的存在,那么其余数字必定都可以/ 2
,所以可以相当于dp[i / 2]
。
代码如下:
1 |
|