基本思想：
第一次见到完全背包问题，并且这个背包问题所描述的并非整体最大值的问题，而是放置次数的问题；
很多案例没有讲出为神马要这么遍历dp数组，这里说一下：
1.首先，对于n个放置元素的确定，采用打表进行；
2.dp[0]=1，是为了边界初始化，来保证dp[1]当放置元素为1时，可以正常进行初始化，值得注意的是，dp数组内放的是当前值的方案个数；
3.对于dp数组初始化，可以直接从1-n进行放置元素举例，但是不同于寻常的放置元素的转换方程，求放与不放的最大值；
而是dp[j]=dp[j]+dp[j-n];
原因在于，当我们决定要放n种元素的时候，就要去寻找之前n占位时，剩余容量能放多少种，也就是dp[j-n]。而由于当我们在枚举第n种元素前，就已经研究过1-n-1种元素在当前容量有放置有几种方案，所以要再加上dp[j];
关键点：
后续在刷题吧，第一次见到这种dp内存储方案数目的dp数组；
01背包问题中也仅仅是直接记录放置情况；
链接：https://www.nowcoder.com/questionTerminal/376537f4609a49d296901db5139639ec?f=discussion
来源：牛客网
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib> //rand ( ), srand ( )
#include <ctime> //time ( )
using namespace std;
int n, dp[1000002], a[21];
int main ( )
{
int i, j, t;
for ( i = 1; i <= 20; i ++ )
a[i] = ( 1 << ( i - 1) );
dp[0] = 1;
while ( cin >> n )
{
memset ( dp + 1, 0, sizeof ( dp ) );
for ( i = 1; i <= 20; i ++ )
{
for ( j = a[i]; j <= n; j ++ )
{
dp[j] += dp[j - a[i]];
dp[j] %= 1000000000;
}
}
cout << dp[n] << endl;
}
return 0;
}
原文：https://www.cnblogs.com/songlinxuan/p/12388991.html