Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Solution: Maximum Ribbon Cut

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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, {})
A

Anonymous

· 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.

A

Anonymous

· 5 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%


Vote for new content