Leetcode - Coin Change (Python)

Рет қаралды 13,907

Timothy H Chang

Күн бұрын

Пікірлер: 12

@tokonehkalango1712 10 ай бұрын

Love your videos, they're very helpful and probably the best I've seen for leetcode problems

@janmichaelaustria620 3 жыл бұрын

There's also a BFS solution to this problem, which I thought was super cool! We can say the minimum coins need would be the minimum path from root to the needed amount. Then its similar to good old BFS! if not amount: return 0 visited = [False]*(amount+1) visited[0] = True q = deque([(0,0)]) while q: curr_amount, coinsUsed = q.popleft() #take coin coinsUsed += 1 for c in coins: #incremtn amount by the count next_amount = curr_amount + c if next_amount == amount: return coinsUsed #if we can still keep going if next_amount < amount: #check we havent seen this amount yet if visited[next_amount] == False: visited[next_amount] = True q.append((next_amount,coinsUsed)) return -1

@gempf 3 жыл бұрын

Hello, how can i do to past this test: import unittest from change import find_fewest_coins # Tests adapted from `problem-specifications//canonical-data.json` class ChangeTest(unittest.TestCase): def test_single_coin_change(self): self.assertEqual(find_fewest_coins([1, 5, 10, 25, 100], 25), [25]) def test_multiple_coin_change(self): self.assertEqual(find_fewest_coins([1, 5, 10, 25, 100], 15), [5, 10]) def test_change_with_lilliputian_coins(self): self.assertEqual(find_fewest_coins([1, 4, 15, 20, 50], 23), [4, 4, 15]) def test_change_with_lower_elbonia_coins(self): self.assertEqual(find_fewest_coins([1, 5, 10, 21, 25], 63), [21, 21, 21]) def test_large_target_values(self): self.assertEqual( find_fewest_coins([1, 2, 5, 10, 20, 50, 100], 999), [2, 2, 5, 20, 20, 50, 100, 100, 100, 100, 100, 100, 100, 100, 100], ) def test_possible_change_without_unit_coins_available(self): self.assertEqual(find_fewest_coins([2, 5, 10, 20, 50], 21), [2, 2, 2, 5, 10]) def test_another_possible_change_without_unit_coins_available(self): self.assertEqual(find_fewest_coins([4, 5], 27), [4, 4, 4, 5, 5, 5]) def test_no_coins_make_0_change(self): self.assertEqual(find_fewest_coins([1, 5, 10, 21, 25], 0), []) def test_error_testing_for_change_smaller_than_the_smallest_of_coins(self): with self.assertRaisesWithMessage(ValueError): find_fewest_coins([5, 10], 3) def test_error_if_no_combination_can_add_up_to_target(self): with self.assertRaisesWithMessage(ValueError): find_fewest_coins([5, 10], 94) def test_cannot_find_negative_change_values(self): with self.assertRaisesWithMessage(ValueError): find_fewest_coins([1, 2, 5], -5) # Utility functions def assertRaisesWithMessage(self, exception): return self.assertRaisesRegex(exception, r".+") if __name__ == "__main__": unittest.main()

@tu4012 2 жыл бұрын

what's the time complexity?

@saimanasayadlapalli2225 2 жыл бұрын

Above solution throws error unless else case is changed to integer class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float('inf') for i in range(amount + 1)] dp[0] = 0 for a in range(len(dp)): for c in coins: if a-c>= 0: dp[a] = min(dp[a], dp[a-c]+1) return -1 if dp[-1] == float('inf') else int(dp[-1])

@edwardteach2 3 жыл бұрын

class Solution(object): def coinChange(self, coins, amount): """ :type coins: List[int] :type amount: int :rtype: int """ dp = [float('inf')] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for c in coins: if i - c >= 0: dp[i] = min(dp[i], 1 + dp[i-c]) return dp[amount] if dp[amount] != float('inf') else -1

@arpitsaxena239 3 жыл бұрын

you need to make this video again .. not able to understand how dp[i]=min(dp[i], dp[i-c]+1) is working? 🤔

@leoyou4790 2 жыл бұрын

dp always track the minimum combination of coin to make up to i. dp[i] means current minimum combination , and dp[i-c]+1 means the combination if I take current coin, so we need to update dp[i] each coin to find the minimum combination.

@balavikashkandukuri6139 2 жыл бұрын

@@leoyou4790 could u make it more clear