抵达终点的最小跳数

给定一个非负整数数组&＃xff0c;最初你被放在数组的第一个元素上&＃xff0c;数组的每个元素代表你能跳的最大的步数。你的目标是用最少的跳数抵达最后一个元素。

例如&＃xff0c;给定A &＃61; [2,3,1,1,4]&＃xff0c;抵达终点的最小跳数是2&＃xff08;下标0->下标1->下标4&＃xff09;。

思路一&＃xff1a;

table[i]表示从数组下标i的位置抵达最后一个元素的最少跳数。对于在下标i用1跳抵达的地方&＃xff08;最远跳arr[i]&＃xff0c;最近跳1跳&＃xff09;&＃xff0c;可以写出状态转移方程&＃xff1a;

table[i]&＃61;table[i&＃43;k]&＃43;1&＃xff0c;(1<&＃61;k<&＃61;arr[i])

从后往前&＃xff0c;逐渐建立一维table&＃xff0c;table[0]即为所求。复杂度是O(n^2)。

代码如下&＃xff1a;

class Solution {
public:int jump(int A[], int n) {int *table &＃61; new int[n];table[n-1] &＃61; 0;for (int i &＃61; n-2; i >&＃61;0; i--) {if (A[i] &＃61;&＃61; 0)table[i] &＃61; INT_MAX;else if (A[i] >&＃61; n - i - 1)table[i] &＃61; 1;else {int min &＃61; INT_MAX;for (int j &＃61; i&＃43;1; j table[j])min &＃61; table[j];} if (min !&＃61; INT_MAX)table[i] &＃61; min &＃43; 1;elsetable[i] &＃61; min;}}return table[0]; }
};

思路二&＃xff1a;

table[i,j]表示从下标i到下标j需要的最小跳数。那么状态转移方程是&＃xff1a;

if arr[i]&＃43;i>&＃61;j

      then table[i,j]&＃61;1

else

    table[i,j]&＃61;min{table[i,k]&＃43;table[k,j]}, (i

复杂度是O(n^3)。