Why does 0/1 Knapsack problem need a 2-D array to memoize whereas House Robber problem need a 1-D array?

Question

I'm asking this in reference to Dynamic Programming, I'm a beginner at it. I understood the House Robbers problem nicely and found 0/1 Knapsack similar to it. But I tried to code it up in similar way using 1-D array but it gave wrong answers. The solution had a 2-D array which is confusing me that why is there a need for 2-D array to store the remaining/occupied weight, as during recursion we are already passing the remaining/occupied weight. Any help would be appreciated.

def knapSack(self,sackw, weights, values, n):
    # my approach using a 1-D array to memoize
    dp = [-1]*n
    def recur(i, weightleft):
        if weightleft <= 0 or i >= n:
            return 0
        if weights[i] > weightleft:
            return recur(i+1, weightleft)
        if dp[i] != -1:
            return dp[i]
        else:
            res = dp[i] = max(values[i] + recur(i+1, weightleft - weights[i]), recur(i+1, weightleft))
        return res
    
    return recur(0, sackw)

The given answer using 2-D array below

def solve_knapsack(profits, weights, capacity):
    dp = [[-1 for x in range(capacity+1)] for y in range(len(profits))]
    return knapsack_recursive(dp, profits, weights, capacity, 0)
    def knapsack_recursive(dp, profits, weights, capacity, currentIndex):

      # base checks
        if capacity <= 0 or currentIndex >= len(profits):
            return 0

  # if we have already solved a similar problem, return the result from memory
        if dp[currentIndex][capacity] != -1:
            return dp[currentIndex][capacity]

  # recursive call after choosing the element at the currentIndex
  # if the weight of the element at currentIndex exceeds the capacity, we
  # shouldn't process this
        profit1 = 0
        if weights[currentIndex] <= capacity:
            profit1 = profits[currentIndex] + knapsack_recursive(
        dp, profits, weights, capacity - weights[currentIndex], currentIndex + 1)

  # recursive call after excluding the element at the currentIndex
        profit2 = knapsack_recursive(
    dp, profits, weights, capacity, currentIndex + 1)

        dp[currentIndex][capacity] = max(profit1, profit2)
        return dp[currentIndex][capacity]

Test Cases:

1. weights = [4,5,1], values = [1,2,3], n = 3, sackweight = 4. Expected output = 3.

Only this one runs. The rest give wrong answer. They are too big to post here.

Answer 1

"found 0/1 Knapsack similar to it"

From what I understand, this assumption is incorrect.

In 0/1 Knapsack problem, you have to maximize the value and keep the total weight under a given limit. There's no restriction on the item ordering that you select (basically, no constraint like "you can't select three consecutive items" or so). Since you're maintaining three properties in the DP state (index, weight, value of each item) you use 2D DP.

In the House Robbers problem, you're maximizing the value without having to keep a check on the count/weight of houses robbed. You just have to avoid picking consecutive houses (which can be done using indexes, no additional property needed). So it requires only 2 properties (house value and index), it is done using 1D DP.

A small note on why your 1D approach is incorrect:

Let's say your dp table has a value dp[5] = 10, which was calculated for a weight of x. Let's say your recursively reach i=5 again, but with a different weight this time. Your dp[5] = 10 will get returned, which is incorrect because a different weight might lead to a different possible value.