2 条题解
-
1
#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
- 上传者