The Jumping Kangaroo Problem (Dynamic Programming + Greedy Algorithm)


A kangaroo is at one side of the river. There are N springs in the river, each is separated 1 meter, like this:

K| . . . . . . |

The dots are springs and when the kangaroo jumps on the springs, it can jump further given the strength of the spring. For example, if a spring has strength 5, the kangaroo can jump at distance 5 meter. If it is zero, then the kangaroo will be stuck.

The river is N meters wide, and the kangaroo stands on the first spring. The kangaroo jumps over the last spring and it will be considered as crossing the river. You are given an array of integers representing the strengths for each spring, compute the minimal jumps it takes to cross the river, or -1 if the kangaroo cannot do this.

Input N: 1 ≤ N ≤ 10000
and the second line is an array of integers delimited by space. For example,
5
2 0 1 1 1

Output: 4

The intuitive solution will be building a search tree and use Breadth First Search (BFS) as the kangaroo is jumping. However, given the size of the problem (N maximum 10K), the degree and depth of the tree will be considerably too large for computers to find out a shortest number of jumps given a reasonable timescale.

Dynamic Programming

The Dynamic Programming Analysis: Given F(n) to denote the minimal jumps that kangaroo reaches the N-th spring and also we know the strength of the N-th spring is d, we know the answer of F(n+1), F(n+2) .. to F(n+d), which is F(n+k) = min(F(n+k), F(n)+1), k=1..d

F(0)=F(1)=0, the destination F(n+1) is -1.

If the kangaroo can’t reach the other side of the river, F(n+1) will be left -1 or will be set to INT_MAX+1 which causes integer overflow. Otherwise the answer is stored at F(n+1).

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
#include <iostream>
#include <vector>
#include <climits>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> arr(n + 2, n + 1); // springs
    vector<int> ans(n + 2, INT_MAX); // minimal steps to reach each spring
    ans[n + 1] = -1;
    ans[0] = 0;
    ans[1] = 0;
    for (int i = 1; i <= n; ++ i) {
        cin >> arr[i]; // input
    }
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= arr[i] && i + j <= n + 1; ++ j) {
            if (ans[i + j] == -1) {
                ans[i + j] = ans[i] + 1;
            } else {
                ans[i + j] = min(ans[i + j], ans[i] + 1);
            }
        }
    }
    cout << (ans[n + 1] < 0 ? -1 : ans[n + 1]) << endl; 
    return 0;
}
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n + 2, n + 1); // springs
    vector<int> ans(n + 2, INT_MAX); // minimal steps to reach each spring
    ans[n + 1] = -1;
    ans[0] = 0;
    ans[1] = 0;
    for (int i = 1; i <= n; ++ i) {
        cin >> arr[i]; // input
    }
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= arr[i] && i + j <= n + 1; ++ j) {
            if (ans[i + j] == -1) {
                ans[i + j] = ans[i] + 1;
            } else {
                ans[i + j] = min(ans[i + j], ans[i] + 1);
            }
        }
    }
    cout << (ans[n + 1] < 0 ? -1 : ans[n + 1]) << endl; 
    return 0;
}

The DP solution has O(N^2) time complexity and O(N) space complexity.

Greedy Algorithm

With the greedy algorithm, we keep tracks of the current furthest distance the kangaroo can jump, the minimal steps it takes so far. The Greedy Algorithm is faster which takes O(N) time complexity and O(1) space complexity if we don’t consider the input spring array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; ++ i) {
        cin >> arr[i]; // spring input
    }
    int best = 0, jump = 0, cur = 0;
    for (int i = 0; i < n; ++ i) {
        best = max(best, i + arr[i]); // current furthest distance
        if (cur == i) { // if the kangaroo can jump to current spring
            jump ++;
            cur = best;               
        }        
    }
    cout << (cur >= n ? jump : -1);
    return 0;
}
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; ++ i) {
        cin >> arr[i]; // spring input
    }
    int best = 0, jump = 0, cur = 0;
    for (int i = 0; i < n; ++ i) {
        best = max(best, i + arr[i]); // current furthest distance
        if (cur == i) { // if the kangaroo can jump to current spring
            jump ++;
            cur = best;               
        }        
    }
    cout << (cur >= n ? jump : -1);
    return 0;
}

Given input 1 0 0 0 0 3 0, the kangaroo cannot cross the river. We have to check if the cur is bigger than n – which isn’t – thus output -1.

See also: Algorithms to Compute the Minimal Number of Hops

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
715 words
Last Post: Sum Up Tree/Sub-Tree Values - Compute Employee Importance via DFS or BFS
Next Post: CleanTalk Review - The Best Paid Cloud Anti-Spam/Security Plugins for WordPress (Akismet Alternative)

The Permanent URL is: The Jumping Kangaroo Problem (Dynamic Programming + Greedy Algorithm)

Leave a Reply