前言
动态规划一定能获得最优解，但是效率并不一定最高。
正文
问题来源
本问题来自leetcode上的45题。用go语言做的
问题描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例 1:
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置
分析：
动态规划思想很简单，就不仔细说了 本人写的Go代码如下：
const INT_MAX = int(^uint(0) >> 1)
func jump(nums []int) int {
len := len(nums)
if 0 == len {
return 0
}
dp := make([]int, len)
j := len - 1
dp[j] = 0
j--
for ; j >= 0; j-- {
steps := nums[j]
min := INT_MAX - 10000
stepTime := 0
for i := j+1; (i < len) && (stepTime < steps); i++ {
if dp[i] + 1 < min {
min = dp[i] + 1
// fmt.Printf("j:%d i: %d min: %d \n",j ,i, min)
}
stepTime++
}
dp[j] = min
}
return dp[0]
}
最朴素的想法是，对于每个位置，挨个尝试一遍不同的跳法，这样总能找到最优解，最坏情况下A[i]=n，那么时间复杂度为O(n^2)。显然会超时，所以在这个朴素的算法上改进。
如果用动态规划求解，考虑如何划分子问题。一个很自然的想法是将起跳点为子问题边界，令p[i]表示从第i个位置起跳，到终点所需最小步数，则代价函数为p[i] = 1 + min{p[i + j]}, (1 ≤ j ≤ A[i])。再分析一下时间复杂度，对于每个p[i]需要循环A[i]次，一共有n个p[i]，所以最坏情况下时间复杂度为O(n^2)，可以看出，动态规划实际上跟朴素算法在时间复杂度上没有区别。
考虑能否使用贪心法，对于每个位置，尽量往最远的地方跳。显然这样只考虑了1跳的情况，比较”短视”，很容易举出反例。
但是，可以把贪心法改进一下，考虑2跳的情况，即贪心的条件是：当前跳跃+下次跳跃的总距离最远。那这样是不是就可以了呢？答案是可以的。反证法：
假设当前由贪心法选择的方案不是最优解，那么一定存在一个最优跳法，它所需要的总步数更少，并且它至少在某一个位置下，当前一跳和下一跳（共2次跳跃）跳的不是最远的。考虑那个位置，如果按照贪心策略，那么得到的跳法（2次跳跃）的活动范围完全覆盖了最优解选择的跳法的范围。这样就保证了，贪心法一定不会错过某一个能跳的特别远的好机会。因此把这个位置的的跳法从最优解替换成贪心策略的跳法，总得跳数不会增加。这样总可以在有限的次数内，把最优解完全替换成了贪心法得到的解，且跳数跟最优解一样，这就跟最优解的定义矛盾了。 看一下贪心法的时间复杂度，虽然在每个起跳位置仍然要枚举A[i]次，但对于每个位置只遍历一遍，所以是O(n)。
回过头来想想：本题的特点是在每个步骤上，可选择的范围是连续的，从1到A[i]。正是这个条件导致了动态规划过于低效以及可以使用贪心法，A[i]表示在i处只能跳A[i]那么远，就不能用贪心法了，动归也不再是O(n^2)的了。
转化为代码时，实际上我们关心的只是前两跳最多能跳多远，所以用range保存第1跳能及的范围，next表示在此基础上第2跳能及的范围。当所处位置尚在第1跳范围内时，更新第2跳的范围，当所处位置超过了第1跳的范围，count加1，表示不得不跳一次，同时将第1跳的范围更新成原先第2跳的范围。如此迭代进行下去。
//go
func jump(nums []int) int {
curr := 0
maxLen := 0
count := 0
ln := len(nums)
for i := 0; i < ln; i++ {
if i > curr {
curr = maxLen
count++
}
if maxLen < i + nums[i] {
maxLen = i + nums[i]
}
}
return count
}
//C i表示当前位置，是从1开始索引的
int jump(int A[], int n) {
int range = 1; // 第1跳能及的最远范围
int next = 0; // 第2跳能及的最远范围
int i = 1;
int count = 0;
while (range < n) {
if (i <= range) {
next = max(next, i + A[i - 1]);
i++;
}
else {
count++;
range = next;
}
}
return count;
}
总结：
多思考是否有简单并且高效的解法
结语
闲来无事的话，多练习练习，做做题。
