educative.io

Why for the Bottom up approach for Dynamic programming, we initialized the dp 2D array with -1?

Courses
,
#1

Why for the Bottom up approach for Dynamic programming, we initialized the dp 2D array with -1?

#2

Hey, did you get your answer? I have same question. I am talking about Target Sum problem.

// populate the sum=0 columns, as we will always have an empty set for zero sum
for(int i=0; i < n; i++)
dp[i][0] = 1;

Not sure why it is 1, should be 0 in my opinion based on what I have understood.

#3

For this case you would want a value that’s not within the possible outcomes otherwise you won’t be able to track if it’s updated. 0 is a possible sum you can get from a subtree but -1 is not.

#4

Hi @Abhinav_Nath_Gupta this confused me as well in the beginning but its not that difficult to understand. Essentially -1 is like their invalid value as the maximum value from any recursive call will at worst be zero.

You could have easily created a hashMap instead of a 2d array like so:

def knapsack_recursive(memo, 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 str(currentIndex) + '_' + str(capacity) in memo:
    return memo[str(currentIndex) + '_' + str(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(
      memo, profits, weights, capacity - weights[currentIndex], currentIndex + 1)

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

  memo[str(currentIndex) + '_' + str(capacity)] = max(profit1, profit2)
  return memo[str(currentIndex) + '_' + str(capacity)]