题目描述

blablabla

样例

二维普通解
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 105;
int dp[N][10005],a[N];
int main()
{
    int v;
    cin>>n>>v;

   // dp[0][0]=1;
    for (int i = 1; i <= n; i ++ ) cin>>a[i];
    for (int i = 0; i <= n; i ++ ){
        dp[i][a[0]]=1;
    }
     //dp[0][a[0]]=1;
    for (int i = 1; i <= n; i ++ ){
        for (int j =0; j <=v; j ++ ){
                dp[i][j]=dp[i-1][j];
                if(j>=a[i])dp[i][j]+=dp[i-1][j-a[i]];
        }
    }
    cout<<dp[n][v]<<endl;
}

 //  根据样例  是求组合  数字的选取顺序无关
 //  很多子问题 不是贪心  dp  
 //  暴力  大概 M^2 超时
 //下标还是个数？？
 //dp[i][j]  数到第i个  能够组成j的方案数目
 //  dp[i][j]=(dp[i-1][j]+dp[i-1][j-a[i]])
 一维优化解
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 105;
int dp[10005],a[N];
int main()
{
    int v;
    cin>>n>>v;

   // 组成0 有一种方案
    for (int i = 1; i <= n; i ++ ) cin>>a[i];

        dp[0]=1;

     //dp[0][a[0]]=1;
    for (int i = 1; i <= n; i ++ ){
        for (int j =v; j >=0; j -- ){

                if(j>=a[i])dp[j]+=dp[j-a[i]];
        }
    }
    cout<<dp[v]<<endl;
}


blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla