题目描述

算法1

求组和数

物品在外面，背包在里面

时间复杂度

参考文献

C++ 代码

#include <iostream>
using namespace std;
const int N = 1010 , mod = 1e9 + 7;
int f[N];

int main(){
    int n;
    cin >> n;
    f[0] = 1;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            f[j] = (f[j] + f[j - i]) % mod;
        }
    }
    cout << f[n] << endl;
    return 0;
}

算法2

求排列数

背包在外面，物品在里面

时间复杂度

参考文献

C++ 代码

#include <iostream>
using namespace std;
const int N = 1010 , mod = 1e9 + 7;
int f[N];

int main(){
    int n;
    cin >> n;
    f[0] = 1;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){

            if(i - j >= 0)
                f[i] = (f[i] + f[i - j]) % mod;
        }
    }
    cout << f[n] << endl;
    return 0;
}