vlambda博客
学习文章列表

输入 : [2,3,1,1,4]输出 : true

输入 : [3,2,1,0,4]输出 : false

算法：动态规划

1. 我们可以把该问题拆分成子问题，从前到后确定每个位置是否可达，用动态规划的思想求解。

2. 建立dp数组，dp[i]表示能否跳到i位。

3. 状态转移关系：如果存在某点j，dp[j]为true且从j可以跳到i，那么dp[i]为true；否则，dp[i]为false。

时间复杂度：O(n^2)，n为数组长度。双重遍历。

空间复杂度：O(n)，n为数组长度。建立的dp[]长度为n。

内层遍历改成从后向前，会比从前向后更节省时间。

仔细想想不难发现：如果可以跳到i点，则说明一定可以跳到i前面的任意一点。所以，如果i位为True，前面的位置一定是True。那么我们就无需开dp数组了，这样空间复杂度可以降到O(1)。

public class Solution {
    /**
 * @param A: A list of integers
 * @return: A boolean
 */
    public boolean canJump(int[] A) {
        if (A.length == 0) {
            return false;
        }
        boolean[] dp = new boolean[A.length];
        dp[0] = true;
        for (int i = 1; i < A.length; i ++) {
            for (int j = 0; j < i; j ++) {
                // 如果之前的j节点可达，并且从此节点可以到跳到i
                if (dp[j] && A[j] + j >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[A.length - 1];
    }
}

算法：贪心法

我们利用贪心思想，实时维护最远可达的位置rightmost

依次遍历每个位置i

1. 如果i在rightmost范围内，说明i可达，我们将rightmost更新为max(rightmost, i + A[i])

2. 如果rightmost大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回True。

3. 如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 。

时间复杂度：O(n)，n为数组长度。一次遍历。

空间复杂度：O(1)。

public class Solution {
    /**
 * @param A: A list of integers
 * @return: A boolean
 */
    public boolean canJump(int[] A) {
        int n = A.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + A[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

不难看出，动态规划和贪心算法是原理有些相似的算法，同一问题利用不同算法解题的思路、难易程度也有所不同，注意不要混淆。