洛谷P1164小A点菜

https://www.luogu.com.cn/problem/P1164
背包问题

这道题不难，本来用滚动数组做是不想发题解了，但是又想试试用二维数组就发现了好多问题。(所以说一道题要尝试不同方法多做几遍)
状态定义 很简单 dp[i][j]:前i个菜，共有j元钱的方案数。
dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]
当j==a[i] 时，dp[i][j]=dp[i-1][j]+1
j
前i个菜，共花j元钱的方案数 就等于j元钱只买 前i个菜 加上 买第i个菜 剩下的j-a[i] 元钱买 前i-1个菜。
首先这题不能拿常规的背包问题去求解，不然会死的很惨 。
常规背包问题一般喜欢初始化 第一行 将第一个菜 在两种情况下枚举(钱够就1，不够为0)。
但是这道题目种明确说了 钱要全部花完！ 这就意味者在只考虑一个菜的情况下，只有拥有钱=菜的价格 时 才算为一种方案。
所以 初始为 当拥有的钱 i 等于 第一道菜的价格 dp[1][i]=1

再来一手滚动数组。
注意：从后往前推
只要注意初始化 dp[0]=1: 当菜的价格和拥有钱相等时 就是一种方案。

#include 
#include 
using namespace std;
int dp[105][10005]={0};
int main(){
    int n,m,a[105];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=0;i<=m;i++) if(i==a[1]) {dp[1][i]=1;break;}
    for(int i=2;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(j 
 
滚动数组
 
#include 
#include 
using namespace std;
int dp[10005]={0};
int main(){
    int n,m,a[105];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0&&j>=a[i];j--){
            dp[j]+=dp[j-a[i]];
        }
    }
    printf("%d",dp[m]);
    return 0;
}