动态规划 方案数问题_动态规划 取数 方案数

#include<bits/stdc++.h>

using namespace std;
const int N=1e4+10;
int f[110][N];
int a[110];
int n,m;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    //f[i][j]代表前i个数中和为j的个数
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j-a[i]>0) f[i][j]+=f[i-1][j-a[i]];
            else if(j-a[i]==0) f[i][j]+=1;
        }
    int ans=0;

    printf("%d",f[n][m]);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

方案选择为什么会想到动态规划呢？
可能是因为符合无后效性的特点，最有子结构
注意：1.初始化的时候if(j-a[i]==0) f[i][j]+=1;
2.f[i][j]+=f[i-1][j-a[i]]; 不要加一

方案数可能会很大 最好用long long

//完全背包

#include<bits/stdc++.h>

using namespace std;
int f[10][1010];
int a[10],n;

int main()
{
    a[1]=10,a[2]=20,a[3]=50,a[4]=100;
    scanf("%d",&n);
    for(int i=1;i<=4;i++)
        for(int j=0;j<=n;j++)
        {
            f[i][j]=f[i-1][j];//f[i][j-a[i]];
            
            if(j-a[i]==0) f[i][j]+=1;
            else if(j-a[i]>0) f[i][j]+=f[i][j-a[i]];
        }

    
    printf("%d",f[4][n]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//完全背包

#include<bits/stdc++.h>

using namespace std;
int f[10][1010];
int a[10],n;

int main()
{
    a[1]=10,a[2]=20,a[3]=50,a[4]=100;
    scanf("%d",&n);
    /*for(int i=1;i<=4;i++)
        for(int j=0;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            if(j-a[i]==0) f[i][j]+=1;
            else if(j-a[i]>0) f[i][j]+=f[i-1][j-a[i]];
        }*/
    
    for(int i=1;i<=4;i++)
        for(int j=0;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            for(int k=1;k*a[i]<=j;k++)
            {
                //f[i][j]=max(f[i][j],f[i-1][j-])
                if(j-k*a[i]==0) f[i][j]+=1;
                else f[i][j]+=f[i-1][j-a[i]*k];
            }
        }
    
    printf("%d",f[4][n]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

注意k要从1开始 要不然会与上面发生重复

注意优化