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

## Recent Activity