2021笔试题——牛牛喜欢数字序列跳跃

作者：小 琛
欢迎转载，请标明出处

牛牛很喜欢在数字序列中跳跃

现在他正站在1号位置,每次跳跃,他可以向后跳一步(即从跳到+1),也可以跳到该位置往后的任意一个与该位置上的数字相间的位置
例如：1，2，3，4，1 ，3，4，1 在第一个1的位置时，既可以跳一个，也可以跳到后面任意一个1的位置
请问他最少需要跳多少步才能跳到N号位?
输入描述:
一个数字序列
输出描述:
最少步数

题目解答：
思路为动态规划+哈希

对于某一个位置F[i]而言，到达该位置的步数只有两种情况：
第一种，F[i]=F[i-1]+1，即等于前一步+1；
第二种，F[i]=F[与vector[i]数值相等的位置]+1

因此，动态规划方程：

1. 当vector[i]已经存在，F[i]=min(F[i-1]+1,F[j]+1)，其中i为当前位置下标，j为对应的前一个该值。注意这里的j必须为第一个该值
2. 当vector[i]不存在，F[i]=F[i-1]+1

初始状态：dp[0]=0;
可以使用哈希来存储每个位置对应的最小值，当遇到相同值的时候，拿出对应的value，判断value+1和dp[i-1]+1谁最小即可

代码的可优化处：经读者建议，用于统计的dp数组可以只用一个值来替代，因为每一个位置的状态仅仅与哈希表中对应值和上一个状态相关，笔者这里便于大家更好的理解，用到了dp数组统计了每一个位置的状态。也欢迎大家写出更优质的代码

代码实现：

int getn(int n, vector<int> vec)
{
	vector<int> dp(n);
	unordered_map<int, int> mp;
	dp[0] = 0;
	mp[vec[0]] = 0;
	for (int i = 1; i < vec.size(); i++)
	{
		if (mp.count(vec[i]))
		{
			dp[i] = min(mp[vec[i]] + 1,dp[i-1]+1);
		}
		else
		{
			dp[i] = dp[i - 1] + 1;
			mp[vec[i]] = dp[i];
		}
	}
	return dp[vec.size() - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20