最小跳数问题
在这个问题中，给出了一个正整数列表。每个整数表示可以从当前元素进行多少个最大步长。从第一个元素开始，我们必须找到到达列表末尾的最小跳转数。
对于动态编程方法，定义了一个跳转数组来存储所需的最小跳转数。像jumps[i]的值一样，它指示从第0个索引到达数组的第i个索引需要多少个最小跳转。
输入输出
Input:
A list of integers. {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output:
The minimum number of jumps to reach the end location. It is 3.
Start from value 1, go to 3. then jumps 3 values and reach 8. then jump 8 values and reach the last element.算法
minPossibleJump(list, n)
输入：Number数组，数组中元素的数量。
输出：到达终点所需的最小跳数。
Begin
define an array named jump of size n
if n = 0 or list[0] = 0, then
return ∞
jump[0] := 0
for i := 1 to n, do
jumps[i] := ∞
for j := 0 to i, do
if i <= j + list[j] and jump[j] ≠ ∞, then
jump[i] := minimum of jump[i] and (jump[j] + 1)
break the loop
done
done
return jump[n-1]
End示例
#include<iostream>
using namespace std;
int min(int x, int y) {
return (x < y)? x: y;
}
int minPossibleJump(int list[], int n) {
int *jumps = new int[n]; // dynamically create jumps array to store steps
if (n == 0 || list[0] == 0)
return INT_MAX;
jumps[0] = 0;
for (int i = 1; i < n; i++) {
jumps[i] = INT_MAX; //initially set jumps as infinity
for (int j = 0; j < i; j++) {
if (i <= j + list[j] && jumps[j] != INT_MAX) {
jumps[i] = min(jumps[i], jumps[j] + 1);
break;
}
}
}
return jumps[n-1];
}
int main() {
int list[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
int size = 11;
cout << "Minimum number of jumps to reach end is: "<< minPossibleJump(list,size);
return 0;
}输出结果
Minimum number of jumps to reach end is: 3