DP after a long time :)

At work it seems I will be shifting from Java to C++ now. I have never coded in C++ before, whenever I have it was solely for the purpose to use their beautiful vector, map, string and all libraries. So I guess I should start doing some C++ coding too. A step towards it, I wrote a C code after a looong time. Obviously, a DP problem to target :D. It is a typical interview problem, just that the O(n) is also possible, and I feel it’s the best one can do.

Problem: Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array (starting from the first element).
Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3
with the sequence : 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
If an element is 0, then cannot make any jumps

PS: Have not checked for corner cases. Laziness again 😛

#include<stdio.h>
#include<stdlib.h>

#define MAX 0x7fffffff

inline int min(int a, int b) {
  return a >= b ? b : a;
}

int find_min_steps(int const * const input, const int n) {
  int min_steps_dp[n], i, temp, next_vacant;
  for (i = 0; i < n; min_steps_dp[i++] = MAX);

  min_steps_dp[0] = 0;
  next_vacant = 1; // Is the index in the array whose min_steps needs to be updated
                   // in the next iteration.
  for (i = 0; i < n && min_steps_dp[n - 1] == MAX; i++) {
    temp = i + input[i];
    if (temp >= n) {
      min_steps_dp[n - 1] = min(min_steps_dp[n - 1], min_steps_dp[i] + 1);
      temp = n - 1;
    } else {
      printf("Updating min[%d] to %d \n", i + input[i], min_steps_dp[i] + 1);
      min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1);
    }
    if (temp > next_vacant) {
      for (; next_vacant < temp; next_vacant++) {
        min_steps_dp[next_vacant]
          = min(min_steps_dp[temp], min_steps_dp[next_vacant]);
      }
    }
  }
  for (i=0;i<n;printf("%d ",min_steps_dp[i++]));printf("\n");
  return min_steps_dp[n-1];
}

int main() {
  int n, *input, i;
  scanf("%d",&n);
  if ((input = (int *)malloc(n * sizeof(int))) == NULL) {
    return -1;
  }
  for (i = 0;i < n; scanf("%d",&input[i++]));
  printf("Minimum steps: %d\n",find_min_steps(input, n));
  return 0;
}

Another Greedy solution provided by Abhishek in O(n) time and O(1) space.

#include <iostream>
#include <vector>

using namespace std;

int find_min_steps(vector<int>& input) {
   int start, end, next_start;
   vector<int> result;
   start = end = 0;
   int n = input.size();

   while (end < n-1) {
     int max = -1;
     for(int w = 0; start <= end ; w++, start++){
       if(input[start] + w > max) {
         max = input[start] + w ;
         next_start = start;
       }
     }
     start = end + 1;
     end = next_start + input[next_start];
     result.push_back(input[next_start]);
   }
   cout << endl << "steps are : ";
   for(int i =0; i< result.size(); ++i)
     cout << endl << result[i];
   cout << endl;
   return result.size();
}

int main() {
  vector<int> input;
  int t = -1;
  cout << endl << "enter input values.. (-1) to end" << endl;
  do {
   cin >> t;
   input.push_back(t);
  } while(t != -1);
  input.resize(input.size() -1); //remove last pushed -1.
  cout << endl << "Minimum steps: "<< find_min_steps(input) << endl;
  return 0;
}

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

9 Responses to DP after a long time :)

  1. abc says:

    Hey can you pls briefly explain the logic? Thanks in advance!

    • Avi Dullu says:

      for each index in input array check the farthest you can go (by keeping another auxiliary array). The trick is to only increment the counter in the auxiliary array (notice that next_vacant is never reset, it only increments and points to the next vacant position in the auxiliary array) and return as soon as next_vacant becomes equal to ‘n’ + 1 (I have checked an equivalent condition of last index being not equal to MAX, which I had set initially).
      Hope this helps.

  2. amit says:

    hi,

    i dont understand how it is O(n)….can u explain?

    thanks

  3. amit says:

    ok i think i get it…can u write the recursive relation for this problem?

    thanks

  4. Avi Dullu says:

    Thanx for the code 🙂
    2 things.
    a. Can you re-post the code using the following scheme
    OPEN_SQUARE_BRACKETsourcecode language=”C”CLOSE_SQUARE_BRACKET
    CODE_HERE
    OPEN_SQUARE_BRACKET/sourcecodeCLOSE_SQUARE_BRACKET
    It will look like the codes that I post.
    OPEN_SQUARE_BRACKET = [
    CLOSE_SQUARE_BRACKET = ]
    b. From a cursory look I see that you have a vector of ints “result” in your program. Which makes the code O(n) space. Maybe if you re-post the code I am more clear.

  5. Abhishek says:

    sorry i pasted your code. my code is

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int find_min_steps(vector<int>& input) {
       int start, end, next_start;
       vector<int> result;
       start = end = 0;
       int n = input.size();
    
       while (end < n-1) {
         int max = -1;
         for(int w = 0; start <= end ; w++, start++){
           if(input[start] + w > max) {
             max = input[start] + w ;
             next_start = start;
           }
         }
         start = end + 1;
         end = next_start + input[next_start];
         result.push_back(input[next_start]);
       }
       cout << endl << "steps are : ";
       for(int i =0; i< result.size(); ++i)
         cout << endl << result[i];
       cout << endl;
       return result.size();
    }
    
    int main() {
      vector<int> input;
      int t = -1;
      cout << endl << "enter input values.. (-1) to end" << endl;
      do {
       cin >> t;
       input.push_back(t);
      } while(t != -1);
      input.resize(input.size() -1); //remove last pushed -1.
      cout << endl << "Minimum steps: "<< find_min_steps(input) << endl;
      return 0;
    }
    
    
  6. Abhishek says:

    plz find my code in comments tagged as “Anonymous on November 16, 2011”

    http://www.careercup.com/question?id=6291664

  7. Abhishek says:

    ok. thanks.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: