We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Jumping on the Clouds
  5. Discussions

Jumping on the Clouds

  • gschoen
     + 0 comments

    In hindsight, this is just a straight application of the greedy algorithm Just make 2 jumps if you can. I wasn't sure of that so I treated this as a dynamic programming problem.

    #define BIGNUM 1000000000

int jumpingOnClouds(int c_count, int* c) {
    int n = c_count;
    int dp[n];
    dp[n-1] = 0;
    if (c[n-2]) dp[n-2] = BIGNUM;
    else dp[n-2] = 1;
    for (int i = n-3; i >= 0; --i) {
        if (c[i]) {
            dp[i] = BIGNUM;
            continue;
        }
        int step1 = 1 + dp[i+1];
        int step2 = 1 + dp[i+2];
        if (step1 > step2) step1 = step2;
        dp[i] = step1;
    }
    return dp[0];
}