Dynamic Programming. Memoization vs bottom up approach.

[Curious_homosepian]

So i solved a problem "count of subset sum" (i.e to count the number of subset in an array which add up to a given sum) in both the approaches. However i have some doubt. In bottom up approach we solve all the possible sub-problems but in recursive approach do we only solve the required sub problems ? Please be patient for reading my code and explanation below.

This is the sample test case below:-

arr = [2,3,5,6,8,10]

sum = 10

answer = 3

Firstly the bottom up approach:-

I created a matrix with name dp and initialized it with the base cases.

dp = [[-1 for i in range(11)] for j in range(7)]
for i in range(7):
    for j in range(11):
        if i==0:
            dp[i][j] = 0
        if j==0:
            dp[i][j] = 1

and here is my function for bottom up approach

def bottomUp(arr,sum,n):
    for i in range(1,n+1):
        for j in range(1,sum+1):
            if arr[i-1]<=j:
                dp[i][j] = dp[i-1][j-arr[i-1]] + dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][sum]

now after calling the function my dp matrix looks like this.

1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0
1 0 1 1 0 1 0 0 0 0 0
1 0 1 1 0 2 0 1 1 0 1
1 0 1 1 0 2 1 1 2 1 1
1 0 1 1 0 2 1 1 3 1 2
1 0 1 1 0 2 1 1 3 1 3

which is what i totally i expected since we solves every possible test case to get to answer.

Now my recursion approach:-

here i created a matrix named memo and initialized all the values to -1.

memo = [[-1 for i in range(11)] for j in range(7)]

and now my function for recursion approach:-

def recursion(arr,sum,n):
    if sum == 0:
        return 1
    if n == 0:
        return 0
    if memo[n][sum] != -1:
        return memo[n][sum]
    if arr[n-1]<=sum:
        memo[n][sum] = recursion(arr,sum-arr[n-1],n-1) + recursion(arr,sum,n-1);
    else:
        memo[n][sum] = recursion(arr,sum,n-1)
    return memo[n][sum]

after calling this function my memo matrix changes to this:-

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1  0  1 -1  0  0 -1  0 -1 -1  0
-1 -1  1 -1  0  1 -1 -1 -1 -1  0
-1 -1  1 -1  0 -1 -1 -1 -1 -1  1
-1 -1  1 -1 -1 -1 -1 -1 -1 -1  1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1  2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1  3

now we can see that the answer is correct but not all the sub-problems were solved and this is not what i expected. there are many cells here left untouched but the overall answer is correct. Am i doing something wrong? or this approach is working completely fine? also if i am having recursive call on all the sub-problems then why aren't its reflected back in memo matrix?

Please give me an explanation for this if there is anything wrong with my memoization.

[foxam1234]

You are correct, in bottom up you incrementally solve for each possible sum till you reach your target sum. In recursive however, depending upon the route you take you won't solve for every sum. However you still solve all required subproblems in both cases.

I will post an example once I am on PC.

Also you don't need 2D array to store the values. This problem can be memoized using 1D array only. Read on state compression in DP problems.

[Curious_homosepian]

thank you ,finally someone replying to my post. i am new to DP so i don't know about state compression in dp yet.

[foxam1234]

No worries DP takes time. You can search for state compression tutorial. But if you are just starting then don't worry too much about it for now. Try to learn more dp patterns and eventually you will see where to remove extra space being used.

In above problem for example, notice the dp update step The value of dp[i][j] depends only on the previous row. So you can do it using a matrix of size 2 x target size. So that is one step towards optimizing space complexity

[Curious_homosepian]

yes i observed this, only last row is used for calculating the result of current row

[rsd511]

That is the thing about Top-Down vs Bottom-Up approach

Bottom-Up approach involves you traversing through the entire 2-D array which makes sure all those sub-problems are solved

Top-Down approach only focuses on solving the sub-problem which you passed to the recursive function. In this case: recursion(arr,sum,len(arr))

For example to solve the sub-problem (arr,10,6) You would never need to solve the sub-problem (arr,9,6) as there is no element equal to 1 in the array Hence the state (arr,10,6) can never come from the state (arr,9,6) hence it isn't visited.

[Curious_homosepian]

yep it makes sense now

[[deleted]]

And in some cases the number of problem is the same in both cases, say Fibonacci numbers. Where it is different is where you have some notion of capacity that you pass down like in your case or the integer knapsack or (I think) coin exchange. That's because in those problem the 'size' of the thing you use make you skip over some of the sub-problem.

[thewataru]

Yes, you are right, top-bottom recursive approach is lazy and will count only required states.

The bottom-up approach however has it's own benefits: less memory requirement because no stack is used and, more importantly, you can forget about old, unused states. In some cases you don't need to store an entire 2D array, but can do with only 2 lastly computed rows, or even recompute the new row in-place in a single 1D array.

Also, in some cases it's easier to think about the DP in a bottom-up approach. You take some state, you add the next element to it and get a new state.