【数字组合】

题目

---

思路

状态表示： $f[i][j]$ 对应考虑1到 i 号数字，和为 j 的方法，表示方法数
目标表示： $f[n][m]$
状态转移： $f[i][j]=f[i-1][j]+f[i-1][j-a[i]]$ 即选和不选
初始化： $f[i][0]=1$ 表示一种方法，注意这里的 $i\in [0,n]$
优化: 见代码

---

代码

#include <bits/stdc++.h>
using namespace std;
int f[110][10010];
int main()
{
    int n, m;
    cin >> n >> m;
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        f[i][0] = 1;
        int a;
        cin >> a;
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = f[i-1][j];
            if(j >= a) f[i][j] += f[i-1][j-a];
        }
    }
    
    cout << f[n][m];
    return 0;
}

---

#include <bits/stdc++.h>
using namespace std;
int f[10010];
int main()
{
    int n, m;
    cin >> n >> m;
    
    f[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        for(int j = m; j >= a; j--)
        {
            f[j] += f[j-a];
        }
    }
    
    cout << f[m];
    return 0;
}

原文地址：https://blog.csdn.net/m0_73669127/article/details/142300348

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！