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