题解 P1164 【小A点菜】
代码和楼上楼下的都差不了太多，我就来解释一下如何推出来下面的这个式子的吧
f[j]+=f[j-a[i]]
过程1
f[i][j]表示前i个菜品恰好花费j元的方案数
然后我们来考虑如何转移：
首先，因为f数组存储的是方案数，所以思路可以是它可以由那些方案转移过来
1.第一种可行的方案是买当前第i道菜品，这个时候前i-1个物品所需要的钱应该是j-a[i], 也就是说前i个物品中所有能凑出j-a[i]元的方案再加上当前这道菜品，就可以变成前i个物品所需的钱为j的方案数。即f[i][j]+=f[i-1][j-a[i]]
2.不买当前第i道菜品，这时候，也就是前i-1个物品凑成j的方案，即f[i][j]+=f[i-1][j];
注意这里是方案的叠加，因为每一种方案都是可行的。
你可能以为现在已经结束了，但实际上你还没有考虑一种方案，当前第i种物品恰好为j元钱，所以可以只买它自己。这种情况其实包含在1中，但是由于f[i][0]=0，所以不会算入这种情况。所以我们要把所有的f[i][0]更新成1，这样就可以计算上面所述的那种情况。
然后你就可以得到一份这样的代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 110
using namespace std;
int n,m,a[N],f[N][10010];
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=0;i<=n;i++) //注意这里要从0开始
f[i][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
f[i][j]+=f[i-1][j];
if(j>=a[i])
f[i][j]+=f[i-1][j-a[i]];
}
cout<<f[n][m];
return 0;
}过程2
接下来就是如何把数组从2维降到1维了
我们先来考虑这样的一个问题，我们要输出a*b的答案，如果硬要用数组做的话可以用一个for循坏从1到a然后另s[i]=s[i-1]+b;最后输出s[a]。
但是通常情况下，我们都是直接用s+=b来实现这个问题，这就是一种数组降维。为什么可以降下来，因为这个问题我们每一次只会使用到i-1，而i-1就是上一次做完留下来的值，所以根本不需要用数组来做这个问题。
然后回到原问题，我们发现f数组的第一维每次也只是使用到了i-1，所以说我们可以给f数组降维。
但是这个时候需要注意一个问题，我们的第二层for循环不能正着跑了，为什么？我们可以观察一下下面两幅图片
第一个图片表示倒着跑，这个时候遍历到的当前的j就是上一次的j
而第二个图片，遍历到的j是刚刚更新了一次的j
最终代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 110
using namespace std;
int n,m,a[N],f[10010];
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=m;j>=a[i];j--)
f[j]=f[j]+f[j-a[i]];
cout<<f[m];
return 0;
}
我的蒟蒻思维，没有跳跃，供蒟蒻使用