Teaching Kids Programming – Brick Layout (Unlimited Knapsack) via Top Down Dynamic Programming Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of integers bricks and integers width and height. Each bricks[i] represents a 1 x bricks[i] size brick. Return the number of ways to lay the bricks such that we get full layout of bricks with width width and height height. Bricks can be reused but can only be laid horizontally. Answer fits within 32-bit integer.

Constraints
1 ≤ n ≤ 1,000 where n is the length of bricks
1 ≤ width * n ≤ 100,000
Example 1
Input
bricks = [2, 3]
width = 5
height = 2
Output
4
Explanation
We can lay the first row of bricks with [2, 3] or [3, 2] and we can lay the second row of bricks with [2, 3] or [3, 2].

Example 2
Input
bricks = [2, 2]
width = 2
height = 1
Output
2
How can you use previous results in the computation for number of ways to arrange bricks at width w.
What is the relationship between each layer?

Brick Layout (Unlimited Knapsack) via Top Down Dynamic Programming Algorithm

This is another classic knapsack variant where you have n-type of items (bricks) to pack in a knapsack with capacity W. We can re-use the same item as many times as possible, find out the number of the ways to pack full the knapsack. There are H rows, meaning the answer is F(W)^H.

Given F(W) represents the number of ways to pack knapsack/wall with width W – it is the sum of F(W-i) where i belongs to bricks and W is larger or equal to i.

Top Down Dynamic Programming Algorithm is usually implemented via Recursion with Memoization to shorten the computation time. The following DP code runs at O(WH) time and O(W) space complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def knapsack(self, bricks, width, height):
        @cache
        def f(n):
            if n < 0:
                return 0
            if n == 0:
                return 1
            ans = 0
            for i in bricks:
                ans += f(n - i)
            return ans
        return f(width)**height

class Solution:
    def knapsack(self, bricks, width, height):
        @cache
        def f(n):
            if n < 0:
                return 0
            if n == 0:
                return 1
            ans = 0
            for i in bricks:
                ans += f(n - i)
            return ans
        return f(width)**height

This can be converted to Bottom-up Dynamic Programming Algorithm: Teaching Kids Programming – Brick Layout (Unlimited Knapsack) via Bottom Up Dynamic Programming Algorithm

Knapsack Problems

• Teaching Kids Programming - 0/1 Knapsack: Length of the Longest Subsequence That Sums to Target (Recursion+Memoization=Top Down Dynamic Programming)
• Teaching Kids Programming - 0/1 Knapsack Space Optimised Dynamic Programming Algorithm
• Teaching Kids Programming - Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem
• Teaching Kids Programming - 0/1 Knapsack Problem via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Bottom Up Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Top Down Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Top Down Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Recursive BackTracking Algorithm
• Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem
• Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem
• Classic Unlimited Knapsack Problem Variant: Coin Change via Dynamic Programming and Depth First Search Algorithm
• Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm
• Complete Knapsack Problem
• 0/1 Knapsack Problem
• Teaching Kids Programming - Combination Sum Up to Target (Unique Numbers) by Dynamic Programming Algorithms
• Algorithms Series: 0/1 BackPack - Dynamic Programming and BackTracking
• Using BackTracking Algorithm to Find the Combination Integer Sum
• Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm
• Partition Equal Subset Sum Algorithms using DFS, Top-Down and Bottom-up DP

–EOF (The Ultimate Computing & Technology Blog) —