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!
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, {})
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.

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

Reading Progress

0%