leetcode

Problem Definition

Given an size $n$ array $a$

Let $J_i$ be a possibility to jump from start index $0$ to last index $i$

Naive

We start from the first position and jump to every index that is reachable. We repeat the process until last index is reached. It takes $O(2^n)$

Dynamic Programming

Recursion \(J_i = \begin{cases} True & \text{if } i = 0 \\ \bigcup_{k=0}^{i-1} (J_k \and (a_k \ge i-k)) & \text{if }i\ge0 \end{cases}\)

Warning: Boolean values cannot notify memoization before it called. Therefore, `memo` array can be used in order to check memoization was happend.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
 * test.cpp
 *
 *  Created on: Feb 12, 2020
 *      Author: swyoo
 */

#include <iostream>
#include <vector>
#include <cstdio> // import stdin, freopen
#include <map>

using namespace std;
typedef map<int, bool> map2b;
class Solution {
public:
    // O(n^2): too slow so, time limit exceed.
	bool canJump(vector<int>& a){
		map2b m;
		# define m(i) m.find(i)->second
		return lookup(a, a.size() - 1, m);
	}
	bool lookup(vector<int>& a, int i, map2b& m){
		if (i == 0)
			return true;
		if (m.find(i) != m.end()) // if memo exist
			return m(i);
		bool loc = false;
		for (int k = 0; k < i; ++k) {
			loc = loc || (lookup(a, k, m) && (a[k] >= i - k));
		}
		m.insert({i, loc});
		return loc;
	}
};

int main() {
	freopen("input.txt", "r", stdin);
	vector<int> A;
	int n, e;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> e;
		A.push_back(e);
	}
	Solution sol;
	bool ans = sol.canJump(A);
	cout << ans <<endl;
	return 0;
}

Of course, bottom up approach can be used, this cannot exceed time limit.

1
2
3
4
5
6
7
8
9
10
11
12
13
// O(n^2) bottom up approach
bool canJump_DP(vector<int>& a) {
    int n = a.size();
    bool* j = new bool[n];
    j[0] = true;
    for (int i = 1; i < n; ++i) {
        j[i] = false;
        for (int k = 0; k < i; ++k) {
            j[i] = j[i] || (j[k] && (a[k] >= i - k));
        }
    }
    return j[n - 1];
}

Greedy

More efficient way exist!

If you think about this problem precisely, you can notice that there are many ways to get a solution.

In this example greedy choice property can be satisfied.

2 greedy choice

  • backward: take the last element among being reachable!
  • forward: take the first element among being reachable!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// backward
bool canJump_greedy(vector<int>& a) {
    int n = a.size();
    int last = n - 1;
    for (int i = n - 2; i >= 0; i--) {
        if (i + a[i] >= last) last = i;
    }
    return last <= 0;
}

// forward
bool canJump_greedy2(vector<int>& a) {
    int n = a.size();
    int maxj = a[0];
    for (int i = 0; i <= maxj; i++) {
        maxj = max(maxj, i + a[i]); // greedy choice 
        if (maxj >= n - 1) return true;
    }
    return false;
}

if you want to run this code, you can visit my github.

Leave a comment