Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Maximum Ribbon Cut

Introduction

We are given a ribbon of length ‘n’ and a set of possible ribbon lengths. We need to cut the ribbon into the maximum number of pieces that comply with the above-mentioned possible lengths. Write a method that will return the count of pieces.

Example 1:

n: 5
Ribbon Lengths: {2,3,5}
Output: 2
Explanation: Ribbon pieces will be {2,3}.

Example 2:

n: 7
Ribbon Lengths: {2,3}
Output: 3
Explanation: Ribbon pieces will be {2,2,3}.

Example 3:

n: 13
Ribbon Lengths: {3,5,7}
Output: 3
Explanation: Ribbon pieces will be {3,3,7}.

.....

.....

.....

Like the course? Get enrolled and start learning!
L

Lucifer

· 4 years ago

In the brute-force solution, why '+1' is added to result ?

if(result != Integer.MIN_VALUE){ c1 = result + 1; }

Show 5 replies
U

UndergroundSkye

· 4 years ago

In the bottom up approach, why is the code checking this (dp[i][t-ribbonLengths[i]] != Integer.MIN_VALUE), taken from the below Java if statement?

if(t >= ribbonLengths[i] && dp[i][t-ribbonLengths[i]] != Integer.MIN_VALUE) dp[i][t] = Math.max(dp[i][t], dp[i][t-ribbonLengths[i]]+1);

This seems like it would only be necessary if there was a constraint saying you need to use the entire ribbon. But since we do not have that constraint this would cause this solution to fail in certain cases.

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

import math

class Solution:
  def countRibbonPieces(self, lengths, total):
    
    def dp(index, acc, count, memo):
      if (index, acc) in memo:
        return memo[(index, acc)]

      if acc > total or index == len(lengths):
        return 0

      if acc == total:
        return count

      with_item = dp(index, acc + lengths[index], count + 1, memo)
      without_item = dp(index + 1, acc, count, memo)

      result = max(with_item, without_item)

      memo[(index, acc)] = result

      return result
      
    return dp(0, 0, 0, {})