#include<iostream> using namespace std; int n,m,k,T; int a[10001],dp[10001]; int main() { cin >> n >> m >> k; for(int i=1; i<=n; i++) { dp[i]=99999; a[i]=0; } for(int i=1; i<=m; i++) { int j; cin>>j; a[j]=1; }// if(a[1]==1) dp[1]=1; else dp[1]=0; for(int i=1; i<=n; i++) { for(int j=1; j<=k; j++) { if(i+j>n) break; if(dp[i]+a[i+j]<dp[i+j]) dp[i+j]=dp[i]+a[i+j]; } } cout<<dp[n]<<endl; return 0; }
时间: 2024-03-19 07:41:58 浏览: 16
这是一段 C++ 代码,看起来像是一个动态规划算法。它的功能是计算在长度为 n 的序列中,从第一个位置出发,每次可以向后跳 j (j<=k) 个位置,且必须经过标记过的位置(标记在数组 a 中),最少需要跳多少次才能到达最后一个位置。其中,输入的参数 n、m、k 分别表示序列长度、标记的位置个数和最大跳跃步数。请问您有什么问题或需要进一步解释的地方吗?
相关问题
#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;
}
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.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)