[C++]LeetCode: 103 Jump Game （局部最优和全局最优法）

浏览数：28 / 时间：2015年06月08日

题目：

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

思路：动态规划求解，我们维护两个变量，一个局部最优，一个全局最优。一个表示到目前为止我们能达到的最远距离，即local = A[i]+i, 另外一个是当前一步出发能跳到的最远距离，global = max(global, local). 确定了递推关系，递推终止条件，达到数组末尾，如果global > n-1, 说明我们可以用抵达数组的末尾（global表示最大距离，我们可以选择刚好的步伐达到末尾）。

复杂度：遍历一次，O(N)，空间O(1)

Attention:

1. 空数组，返回false

if(n == 0) return false;

2. 跳跃时，我们需满足两个条件，i < n && i <= reach, 我们不能够超出全局的最远距离。

for(int i = 0; i < n && i <= reach; i++)

AC Code:

class Solution {
public:
    bool canJump(int A[], int n) {
        if(n == 0) return false;
        int reach = 0; //全局最远距离
        
        for(int i = 0; i < n && i <= reach; i++)
        {
            reach = max(A[i]+i, reach);
        }
        
        if(reach >= n-1)
            return true;
        else
            return false;
    }
};

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

[C++]LeetCode: 103 Jump Game （局部最优和全局最优法）