#include <iostream> using namespace std; int main() { int n; cin >> n; int dp[4][n/10+1]; int c[4] = {0, 10, 20, 50}; // 面额列表 // 初始化 for (int i = 0; i <= n/10; i++) { dp[1][i] = 1; } for (int i = 2; i <= 3; i++) { for (int j = 0; j <= n/10; j++) { dp[i][j] = 0; } } // 递推 for (int i = 2; i <= 3; i++) { for (int j = 1; j <= n/10; j++) { dp[i][j] = dp[i-1][j]; if (j >= c[i]) { dp[i][j] += dp[i][j-c[i]]; } } } // 输出结果 cout << dp[3][n/10] << endl; return 0; }
时间: 2024-01-16 08:05:02 浏览: 24
这是一个兑换零钱的问题,使用动态规划算法可以解决。其中,dp[i][j] 表示使用前 i 种面额的硬币兑换 j 元钱的方案数。则最终答案为 dp[3][n/10],其中 3 表示有三种面额的硬币。
初始化 dp 数组,当只使用第一种面额的硬币时,对任意 j,都只有一种兑换方式。即 dp[1][j] = 1。
然后考虑递推公式。假设我们已经求出了 dp[i-1][j],现在需要求出 dp[i][j]。那么我们可以分为两种情况:
1. 不使用第 i 种面额的硬币。这种情况下,兑换方案数为 dp[i-1][j]。
2. 使用若干枚第 i 种面额的硬币。这种情况下,兑换方案数为 dp[i][j-c[i]],其中 c[i] 表示第 i 种面额的硬币的面额。
因此,递推公式为:
dp[i][j] = dp[i-1][j] + dp[i][j-c[i]]。
最终的答案为 dp[3][n/10]。
下面是 C++ 代码实现:
相关问题
#include <iostream>#include <cstring>using namespace std;const int N = 1e6 + 10, MOD = 1e9 + 7;int n;int dp[N];int main(){ cin >> n; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i ++) dp[i] = (dp[i - 1] + dp[i - 2]) % MOD; cout << dp[n] << endl; return 0;}请将这段代码时间复杂度降低并展示给我
这段代码已经是 $O(n)$ 的时间复杂度,不过可以使用滚动数组进一步优化空间复杂度,将空间复杂度降为 $O(1)$。如下所示:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 1e9 + 7;
int n;
int a = 1, b = 1, c;
int main() {
cin >> n;
if (n == 0) cout << 1 << endl;
else if (n == 1) cout << 1 << endl;
else {
for (int i = 2; i <= n; i++) {
c = (a + b) % MOD;
a = b;
b = c;
}
cout << b << endl;
}
return 0;
}
```
在这个版本中,我们只使用了三个变量 a、b 和 c,避免了使用数组来存储所有的 dp 值,从而将空间复杂度降低为 $O(1)$。
优化这条代码#include <iostream> #include <vector> using namespace std; int longestIncreasingSubsequence(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); int maxLen = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j] + 1); } } maxLen = max(maxLen, dp[i]); } return maxLen; } int main() { int n; cin >> n; vector<int> nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } int result = longestIncreasingSubsequence(nums); cout << result << endl; return 0; }
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestIncreasingSubsequence(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int result = longestIncreasingSubsequence(nums);
cout << result << endl;
return 0;
}
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)