int main() { int dp[3][11]={0}; //for(int i=0;i<11;i++) dp[0][0]=1; for(int i=1;i<=10;i++) for(int j=2;j>=1;j--) for(int k=1;k<=10;k++) if(k>=i) dp[j][k]+=dp[j-1][k-i]; for(int i=0;i<3;i++) { for(int j=0;j<11;j++) cout<<dp[i][j]<<" "; cout<<endl; } return 0; }
时间: 2023-06-23 16:48:27 浏览: 51
这段代码是一个动态规划求解背包问题的例子,其中的dp数组表示在背包容量为k的情况下,使用了j个物品可以得到的最大价值。具体来说,这里的物品是数字1~10,它们的价值和重量都是它们自身的数字大小,而背包的容量则是1~10。该程序使用了三层循环,最内层循环用于更新dp数组,其中的状态转移方程为:dp[j][k]+=dp[j-1][k-i],表示使用第i个物品可以得到的最大价值等于使用前i-1个物品可以得到的最大价值加上使用第i个物品后剩余空间为k-i时得到的最大价值。最终,程序输出了dp数组的所有元素。
相关问题
#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; }
这是一个兑换零钱的问题,使用动态规划算法可以解决。其中,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++ 代码实现:
解决对于30%的数据,保证字符串长度不超过10; 对于60%的数据,保证字符串长度不超过100; 对于90%的数据,保证字符串长度不超过1000; 对于100%的数据,保证字符串长度不超过5000;#include <iostream> #include <string> using namespace std; int main() { string str1, str2; cin >> str1 >> str2; int len1 = str1.size(), len2 = str2.size(); int dp[len1+1][len2+1]; // 定义二维数组dp int ans = 0; // 最长公共子串的长度 // dp数组初始化 for (int i = 0; i <= len1; i++) { for (int j = 0; j <= len2; j++) { dp[i][j] = 0; } } // 动态规划 for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (str1[i-1] == str2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; ans = max(ans, dp[i][j]); // 更新最长公共子串的长度 } else { dp[i][j] = 0; } } } cout << ans << endl; // 输出最长公共子串的长度 return 0; }
这段代码实现了求解两个字符串的最长公共子串长度的问题。根据题目的要求,需要对输入字符串的长度进行限制,可以通过在读入字符串之前进行判断来实现。具体实现如下:
```cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
string str1, str2;
cin >> str1 >> str2;
// 判断字符串长度是否超出限制
if (str1.size() > 5000 || str2.size() > 5000) {
return 0;
}
else if (str1.size() > 1000 || str2.size() > 1000) {
// 对于100%的数据,保证字符串长度不超过5000
// 对于90%的数据,保证字符串长度不超过1000
// 所以如果超过1000但不超过5000,则需要截断字符串
str1 = str1.substr(0, 1000);
str2 = str2.substr(0, 1000);
}
else if (str1.size() > 100 || str2.size() > 100) {
// 对于60%的数据,保证字符串长度不超过1000
// 对于30%的数据,保证字符串长度不超过100
// 所以如果超过100但不超过1000,则需要截断字符串
str1 = str1.substr(0, 100);
str2 = str2.substr(0, 100);
}
else if (str1.size() > 10 || str2.size() > 10) {
// 对于30%的数据,保证字符串长度不超过10
// 所以如果超过10但不超过100,则需要截断字符串
str1 = str1.substr(0, 10);
str2 = str2.substr(0, 10);
}
int len1 = str1.size(), len2 = str2.size();
int dp[len1+1][len2+1];
int ans = 0;
// dp数组初始化
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
dp[i][j] = 0;
}
}
// 动态规划
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1[i-1] == str2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
ans = max(ans, dp[i][j]);
}
else {
dp[i][j] = 0;
}
}
}
cout << ans << endl;
return 0;
}
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)