Is there a rule of thumb for refactoring code to make use of Dynamic Programming concepts?

user_15975040 0
Viewed 51

New to Dynamic Programming.

I have pseudo-code for an algorithm that takes in a list of non-negative integers and the desired sum, then outputs true if the given sum can be made from the given integers (no integers can be used more than once), and false if not. I will post my pseudo-code below. This is how I intuitively solved the problem, and I don't believe it follows dynamic programming concepts.

So my question is: Is there a neat trick for refactoring existing code to follow a more Dynamic Programming approach?

Pseudo-code:

1. Make a 2D boolean array "arr" of size n + 1 row and sum + 1 columns and all cells will be false initially.

2. The value of "arr[i][j]" will be true if there is a subset of list[0..j-1] with a sum equal to i

3. Assign all the values of first column to true  subset[i][0] = true because if target is 0 then it is also possible

4. Assign false to first row "subset[0][i] = false" bacause if sum is not 0 and list is empty, then answer is false

5. Run a for loop from i = 1 to i <= n and for each i do the following 
    // Fill the subset table in botton up manner
    a) Run a for loop from j = 1 to j <= sum and for each j do the following:

    i) if (j < list[i - 1]) then assign arr[i][j] = arr[i - 1][j];
    ii) if (j >= list[i - 1]) or arr[i - 1][j - list[i - 1]] then assign arr[i][j] = arr[i - 1][j]

6. Now if the value of arr[n][sum] is true that means we have a set which sums upto to given target and if it has false then we do not have
dynamic-programming sum algorithm
1 Answers

You pseudocode describes a bottom-up DP algorithm, so-called because it computes solutions to subproblems in a fixed order, from "small" to "large". The order is designed so that, by the time we come to solve a particular subproblem, we have already computed all the solutions to subsubproblems that we need for doing so. Bottom-up DP algorithms usually involve filling a (possibly multidimensional) array in some regular order.

The other kind of DP is a top-down DP. This looks like a recursive function in which the argument values completely determine the subproblem to solve, but with 2 small changes which together are called memoisation (note no "R"):

  1. Before returning the solution value, we store it in a data structure (usually an array or hashtable) keyed by the function argument values, so that it can be quickly found next time the function is called with the same arguments.
  2. Near the top of the function, we check whether the solution to the subproblem described by the arguments has already been solved and stored in the data structure, and if so, return it immediately instead of computing it again.

Neither approach is "better than" the other across the board. If solutions to all possible subproblems are needed to solve the top-level problem, bottom-up is usually faster by a modest constant factor, since memory access patterns are more regular, we can avoid setting up and taking down a stack frame for each subproblem, and we avoid the need to test whether a subproblem has already been solved, which can reduce the number of branch mispredictions. OTOH, top-down solves only the subproblems that need to be solved, so if that is only a small fraction of all possible subproblems, it will be faster.

I personally find it much easier to attack a problem by first looking for a way to solve it recursively; once this is working, it can very easily be turned into a top-down DP algorithm by adding memoisation on top. Only if I'm looking to squeeze the most possible performance out of the algorithm will I then start looking for a subproblem order that would enable a bottom-up DP.

user_479840
Related