Jump Game II

这一题比较容易想到的思路是动态规划，因为直接从前往后分析发现，每次一个结点能到达后面多个节点的时候不知道选哪个，就只能递归，这样会造成很多重复的子问题，于是发现可以倒过来，遍历，这样每次一个节点可以抵达的前方的结点到目的地的距离都是确定的，所以可解。但是正如很多的动态规划算法一样，这个算法的时间复杂度是n^2的，对于大数组很快就超时了。

这题一个比较好的思路就是贪心算法。

这个名词一点出来，就可以按照常规的贪心算法的思路去套用了，当然最重要的就是要证明这里有最优子结构。我们可以发现，仍旧倒过来遍历。例如，从最后一个点开始，一般会有很多点能到达最后一个点，我们认为在这些点中最左边的一个点是最优解必经的一个点（若不只一个最优解，至少有最优解经过它）。

为什么呢？ 例如，有 A B G H Y 五个点（从左至右排列）都能到达目的地，那么A点必在某个最优解的路径上。因为前面的点，如果能到达G H Y之类的，它就肯定能到达A点，反之却未必。

int jump(int A[], int n){
	if (n == 0)
		return 0;
	int index = n - 1;
	int step = 0;
	while (1){
		step++;
		int k = index;
		for (int i = k - 1; i >= 0; i--) {
			if (i + A[i] >= k)
				index = i;
		}
		if (index == 0)
			break;
	}
	return step;
}

Jump Game II

原文：http://www.cnblogs.com/hustxujinkang/p/3995592.html