Solution to LeetCode 322 Coin Change and LeetCode 279 Perfect Squares.
LeetCode 322
Coin Change (Medium) [link]
This is a 0-x Knapsack problem since we can have multiple copies of coins with the same value.
Define dp[j] as the minimum number of coins to have a sum of j. The recurrence relation is dp[j] = min(dp[j], dp[j-coins[i]] + 1). The base case is dp[0]=0, meaning we need 0 coins to sum to 0. Other values should be infinitely large.
In this problem, we don’t care about either we are counting permutations or combinations, so the outer loop can iterate items or capacities. The inner loop should be in the regular order (not reverse).
1] The inner loop iterates coins, and the outer loop iterates amount.
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount+1] * (amount+1)
dp[0] = 0
for i in range(len(coins)):
for j in range(coins[i], amount+1):
dp[j] = min(dp[j], dp[j-coins[i]]+1)
return dp[amount] if dp[amount] <= amount else -1
2] The outer loop iterates amount, and the inner loop iterates coins.
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount+1] * (amount+1)
dp[0] = 0
for j in range(1,amount+1):
for i in range(len(coins)):
if coins[i] <= j:
dp[j] = min(dp[j], dp[j-coins[i]]+1)
return dp[amount] if dp[amount] <= amount else -1
LeetCode 279
Perfect Squares (Medium) [link]
This is a 0-x knapsack problem.
Define dp[j] as the least number of perfect square numbers that sum to j. The recurrence relation is dp[j]= min(dp[j], dp[j-nums[i]]+1).
Since 1 <= n <= 10^4, the size of dp array should be 10^4.
class Solution:
def numSquares(self, n: int) -> int:
nums = [x * x for x in range(1,n+1) if x * x <= n]
dp = [10**4] * (n + 1)
dp[0] = 0
for i in range(len(nums)):
for j in range(1, n+1):
if j >= nums[i]:
dp[j] = min(dp[j], dp[j-nums[i]]+1)
return dp[n]
