Dynamic programming algorithm N, K problem

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 d开发者_如何学编程igits 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.

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.

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.

The trick to solving a dynamic programming problem is usually to figuring out what the structure of a solution looks like, and more specifically if it exhibits optimal substructure.

In this case, it seems to me that the optimal solution with N=12345 and K=3 would have an optimal solution to N=12345 and K=2 as part of the solution. If you can convince yourself that this holds, then you should be able to express a solution to the problem recursively. Then either implement this with memoisation or bottom-up.

The two most important elements of any dynamic programming solution are:

1. Defining the right subproblems
2. Defining a recurrence relation between the answer to a sub-problem and the answer to smaller sub-problems
3. Finding base cases, the smallest sub-problems whose answer does not depend on any other answers
4. Figuring out the scan order in which you must solve the sub-problems (so that you never use the recurrence relation based on uninitialized data)

You'll know that you have the right subproblems defined when

• The problem you need the answer to is one of them
• The base cases really are trivial
• The recurrence is easy to evaluate
• The scan order is straightforward

In your case, it is straightforward to specify the subproblems. Since this is probably homework, I will just give you the hint that you might wish that N had fewer digits to start off with.

Here's what i think:

Consider the first k + 1 digits from the left. Look for the biggest one, find it and remove the numbers to the left. If there exists two of the same biggest number, find the leftmost one and remove the numbers to the left of that. store the number of removed digits ( name it j ).

Do the same thing with the new number as N and k+1-j as K. Do this until k+1 -j equals to 1 (hopefully, it will, if i'm not mistaken).

The number you end up with will be the number you're looking for.