Teaching Kids Programming – Brick Layout (Unlimited Knapsack) via Bottom Up 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 Bottom Up Dynamic Programming Algorithm

Yesterday, we talked about using Top Down Dynamic Programming Approach that is implemented via Recursion with Memoization. We will talk about how to implement/solve the same DP equation using the Bottom-up Dynamic Programming Algorithm.

We need to allocate a DP array and then start solving the DP value from 0 upwards.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def solve(self, bricks, width, height):
        def f(n):
            dp = [1] + [0] * n
            for i in range(n + 1):
                for j in bricks:
                    if i >= j:
                        dp[i] += dp[i - j]
            return dp[-1]     
        return f(width)**height

class Solution:
    def solve(self, bricks, width, height):
        def f(n):
            dp = [1] + [0] * n
            for i in range(n + 1):
                for j in bricks:
                    if i >= j:
                        dp[i] += dp[i - j]
            return dp[-1]     
        return f(width)**height

For each F(N) value, we need to iterate over the bricks and sum up its contribution (F(N-i)). The time and space complexity is O(WH) and it is usually faster (in terms of performance) because there is no recursion involved.

This can be implemented using Top Down Dynamic Programming: Teaching Kids Programming – Brick Layout (Unlimited Knapsack) via Top Down 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) —