首页 > 百度3.30编程1题:数字跳跃
头像
花花加油
编辑于 2021-04-18 09:49
+ 关注

百度3.30编程1题:数字跳跃

牛牛很喜欢在数字序列中跳跃
从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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐