2 条题解

  • 1
    @ 2026-4-5 17:36:20
    #include<bits/stdc++.h>
    using namespace std;
    
    #define ll long long
    const int mod = 1e9 + 7;
    
    int n;
    
    
    int main() {
        cin >> n;
    
        //因为严格递增,所以每个数只能选择一次,那就是从小于等于n的数中选择若干数
        //每个数只能选择一次,最终凑成n的形式,问方案数,因为每个数只能选择一次那就可以用01背包,得到状态数组
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        //dp[i][j]:从前i个数中选取若干数凑成j的总方案数
        dp[0][0] = 1;     //初始化,用于后续递推,且凑成0也为一种方案
    
        for (int i = 1; i <= n; i++)
        {//枚举前i个数
            for (int j = 0; j <= n; j++)
            {//枚举凑成的结果j
                //不选择i:
                dp[i][j] = dp[i - 1][j];
    
                //选择i
                if(j>=i)dp[i][j] = (dp[i][j] + dp[i - 1][j - i]) % mod;
            }
        }
    
        cout << dp[n][n];
    
        return 0;
    }
    
    

    信息

    ID
    47
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    207
    已通过
    71
    上传者