题解 1191: 化学品问题（C++代码），动态规划

解题思路:

此题的简化题为题1233，核电站问题，我有详细解析的题解，可以先去做那个题再来尝试这个题，都是类似的，学会即一通百通。

注意事项:

参考代码:

#include <iostream>
using namespace std;
long long pow(int t)
{
	long long p=1;
	for(int i=0;i<t;i++)p*=2;
	return p;
}
int main()
{
	int l;
	cin>>l;
	for(int k=0;k<l;k++)
	{
		int n,m;
		cin>>n>>m;
		long long dp[50]={0};
		for(int i=0;i<m;i++)
		{
			dp[i]=pow(i);//当i小于m时，方案数等于2的i次方，应该很好理解。 
		}
		if(n<m)
		{
			cout<<dp[n]<<endl;continue;
		}
		else
		{
			for(int i=m;i<=n;i++)
			{
				for(int j=1;j<=m;j++)//dp[i]等于前m个dp的总和。 
				{
					dp[i]+=dp[i-j];
				}
			}
			cout<<dp[n]<<endl;
		}
	}
}