# DP after a long time :)

January 12, 2011 9 Comments

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; }

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

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_vacantis 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.

hi,

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

thanks

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

thanks

Thanx for the code 🙂

2 things.

a. Can you re-post the code using the following scheme

OPEN_SQUARE_BRACKET

sourcecode language=”C”CLOSE_SQUARE_BRACKETCODE_HERE

OPEN_SQUARE_BRACKET

/sourcecodeCLOSE_SQUARE_BRACKETIt 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.

sorry i pasted your code. my code is

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

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

That seems to be correct. Thanx 🙂

ok. thanks.