Dynamic programming algorithm N, K problem

Question

An algorithm which will take two positive numbers N and K and calculate the biggest possible number we can get by transforming N into another number via removing K digits from N.

For ex, let say we have N=12345 and K=3 so the biggest possible number we can get by removing 3 digits from N is 45 (other transformations would be 12, 15, 35 but 45 is the biggest). Also you cannot change the order of the digits in N (so 54 is NOT a solution). Another example would be N=66621542 and K=3 so the solution will be 66654.

I know this is a dynamic programming related problem and I can't get any idea about solving it. I need to solve this for 2 days, so any help is appreciated. If you don't want to solve this for me you don't have to but please point me to the trick or at least some materials where i can read up more about some similar issues.

Thank you in advance.

Answer 1

This can be solved in O(L) where L = number of digits. Why use complicated DP formulas when we can use a stack to do this:

For: 66621542 Add a digit on the stack while there are less than or equal to L - K digits on the stack: 66621. Now, remove digits from the stack while they are less than the currently read digit and put the current digit on the stack:

read 5: 5 > 2, pop 1 off the stack. 5 > 2, pop 2 also. put 5: 6665 read 4: stack isnt full, put 4: 66654 read 2: 2 < 4, do nothing.

You need one more condition: be sure not to pop off more items from the stack than there are digits left in your number, otherwise your solution will be incomplete!

Another example: 12345 L = 5, K = 3 put L - K = 2 digits on the stack: 12

read 3, 3 > 2, pop 2, 3 > 1, pop 1, put 3. stack: 3 read 4, 4 > 3, pop 3, put 4: 4 read 5: 5 > 4, but we can't pop 4, otherwise we won't have enough digits left. so push 5: 45.

Answer 2

Well, to solve any dynamic programming problem, you need to break it down into recurring subsolutions.

Say we define your problem as A(n, k), which returns the largest number possible by removing k digits from n.

We can define a simple recursive algorithm from this.

Using your example, A(12345, 3) = max { A(2345, 2), A(1345, 2), A(1245, 2), A(1234, 2) }

More generally, A(n, k) = max { A(n with 1 digit removed, k - 1) }

And you base case is A(n, 0) = n.

Using this approach, you can create a table that caches the values of n and k.

int A(int n, int k)
{
  typedef std::pair<int, int> input;
  static std::map<input, int> cache;

  if (k == 0) return n;

  input i(n, k);
  if (cache.find(i) != cache.end())
    return cache[i];

  cache[i] = /* ... as above ... */

  return cache[i];
}

Now, that's the straight forward solution, but there is a better solution that works with a very small one-dimensional cache. Consider rephrasing the question like this: "Given a string n and integer k, find the lexicographically greatest subsequence in n of length k". This is essentially what your problem is, and the solution is much more simple.

We can now define a different function B(i, j), which gives the largest lexicographical sequence of length (i - j), using only the first i digits of n (in other words, having removed j digits from the first i digits of n).

Using your example again, we would have:

B(1, 0) = 1

B(2, 0) = 12

B(3, 0) = 123

B(3, 1) = 23

B(3, 2) = 3

etc.

With a little bit of thinking, we can find the recurrence relation:

B(i, j) = max( 10B(i-1, j) + n_i , B(i-1, j-1) )

or, if j = i then B(i, j) = B(i-1, j-1)

and B(0, 0) = 0

And you can code that up in a very similar way to the above.