Solution: 0/1 Knapsack

Grokking Dynamic Programming Patterns for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

DP - Bottom Up - Tabulation Solution | Aren't these two lines the same?

greenwald.juj

Oct 2, 2023

DP - Bottom Up - Tabulation Solution

In the below example, aren't you already initializing the array to 0? So isn't the next for-loop to populate with 0's repetitive? Is there a reason to keep this?

    dp = [[0 for x in range(capacity+1)] for y in range(n)]
    
    # # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    for i in range(0, n):
      dp[i][0] = 0

1

0

Comments

Stanimir Valcheva year ago

On this page

Introduction

Problem Statement

Basic Solution

Code

Top-down Dynamic Programming with Memoization

Code

Bottom-up Dynamic Programming

Code

How to find the selected items?

Challenge

Solution code