题解 | #整数拆分#完全背包问题
整数拆分
https://www.nowcoder.com/practice/376537f4609a49d296901db5139639ec
#include <iostream>
using namespace std;
int dp[1000001];
int main() {
int m;
while (scanf("%d", &m) != EOF) { // 注意 while 处理多个 case
dp[0] = 1;
for (int i = 1, v = 1; v <= m; v *= 2) {
for (int j = v; j <= m; j++) {
dp[j] = (dp[j] + dp[j - v]) % 1000000000;
}
}
printf("%d\n", dp[m]);
}
}
// 64 位输出请用 printf("%lld")
