解题思路:
dp/mdfs
注意事项:
参考代码:
#include <stdio.h> #include <iostream> #include <vector> #define N 110 using namespace std; vector< vector<int> > ans; long long cache[N][N]; long long dp[N][N]; long long solve_dfs_dbg(int preNum, int res, vector<int> arr) { if (res == 0) { ans.push_back(arr); return 1LL; } else if (res < 0) return 0LL; else { long long sum = 0; for (int i = preNum; i <= res; i++) { arr.push_back(i); sum += solve_dfs_dbg(i, res - i, arr); arr.pop_back(); } return sum; } } long long solve_dfs(int preNum, int res) { if (cache[preNum][res] != 0) return cache[preNum][res]; if (res == 0) return 1LL; else if (res < 0) return 0LL; else { long long sum = 0; for (int i = preNum; i <= res; i++) sum += solve_dfs(i, res - i); cache[preNum][res] = sum; return sum; } } long long solve_dp(int n) { for (int i = 0; i <= n; i++) dp[i][0] = 1; for (int i = n; i >= 0; i--) for (int j = 1; j <= n; j++) for (int k = i; k <= j; k++) dp[i][j] += dp[k][j - k]; return dp[1][n]; } int main() { int n = 0; cin >> n; //cout << solve_dfs(1, n) << endl; cout << solve_dp(n) << endl; return 0; }
0.0分
0 人评分
C二级辅导-同因查找 (C语言代码)浏览:553 |
【回文数(二)】 (C++代码)浏览:865 |
【回文数(二)】 (C语言代码)浏览:851 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:623 |
C语言程序设计教程(第三版)课后习题9.2 (Java代码)浏览:608 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:539 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:543 |
【绝对值排序】 (C++代码)浏览:670 |
不容易系列2 (C语言代码)浏览:589 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:608 |