dp专题 可行方案总数：以01背包为例

我们在面对这个相同条件但所求结果不同的问题中
设f[i][j]为前i件物品组合出来的容量为j的方案数
（可以优化成一维）

//无优化：
#include<bits/stdc++.h>
using namespace std;

int a[105];
int dp[100][100]={0};

int main()
{
    int n, s;
    scanf("%d%d",&n,&s);
    for(int i=n;i>=1;i--)
    {
        scanf("%d",&a[i]);
        dp[i][0]=1;
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=s;j++)
        {
            dp[i][j]=dp[i-1][j]+(j>=a[i]?dp[i-1][j-a[i]]:0);
        }
    }
    cout<<dp[n][s]<<endl;

    return 0;
}

//滚动数组优化：
#include<bits/stdc++.h>
using namespace std;

int a[105];
int dp[100]={0};

int main()
{
    int n, s;
    scanf("%d%d",&n,&s);
    for(int i=n;i>=1;i--)
    {
        scanf("%d",&a[i]);
        dp[0]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=s;j>=0;j--)
        {
            dp[j]=dp[j]+(j>=a[i]?dp[j-a[i]]:0);
        }
    }
    cout<<dp[s]<<endl;

    return 0;
}