牛牛很喜欢在数字序列中跳跃
从1号位置，每次可以向后跳一步或跳到往后任意一个与该位置数字相同的位置，问最少几次跳到尾部。
备注：30% N<= 10 ，100% 1<=N<=10^5
in:
5
01212
out: 3
1. 动态规划 + 二维dp数组, 空间复杂度：n^2， 时间复杂度：O(n^2)
第一反应就是这个，二维dp数组存第i位到第j位的步数；这样dp[i][j] = (num[i] == num[j])? 1 : min(dp[i+1][j], dp[i][j-1]) +1;
代码就不贴了，只通过了30%，提示空间复杂度太大了
2. 动态规划 + 一维dp数组，空间复杂度：n， 时间复杂度：O(n^2)
为了减小空间，将二维数组缩小到一维数组，令i从N-1开始慢慢到0，循环N次后就可以得到从0到N-1的最小步数
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
char lis[N];
for(int i=0;i<N;i++){
cin>> lis[i];
}
int left,down;
int dp[N];
for(int i=N-1; i>=0;i--){
dp[i] = 0;
for(int j=i+1; j<N;j++){
if(lis[i] == lis[j]) {
dp[j] = 1;
}
else{
dp[j] = min(dp[j-1] , dp[j]) +1 ;
}
}
}
cout<<dp[N-1]<<endl;
return 0;
} 3. 动态规划 + 辅助数组 + 一维dp数组，空间复杂度：n，时间复杂度：O(n)
有一个可以利用的点，就是数字相同就可以一步到位，所以用一个辅助数组dp1来存储从位置0开始到index的数字最少需要dp1[index]步；这样对于dp每次判断的时候就可以先看看能不能直接跳跃了
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
int nums[N];
char c;
for(int i=0;i<N;i++){
cin>> c;
nums[i] = c-'0';
}
int dp1[10];
fill(dp1,dp1+10,INT_MAX);
int dp[N];
dp[0] = 0;
dp1[nums[0]] = 0;
for(int i=1;i<N;i++){
dp[i] = min(dp[i-1],dp1[nums[i]]) +1;
dp1[nums[i]] = min(dp1[nums[i]], dp[i]);
}
cout<<dp[N-1]<<endl;
return 0;
} 
全部评论
(0) 回帖