Greedy Algorithms

Coin Change Problem

December 23, 2023

medium

dynamic programming, Greedy Algorithms

Problem # Given a set of coin denominations and a target amount, find the minimum number of coins needed to make that amount. Solution # Here’s the Python code for finding the minimum number of coins needed to make a target amount, given a set of coin denominations: def min_coins(coins, amount): # Create a table to store the minimum number of coins for each amount dp = [float('inf')] * (amount + 1) dp[0] = 0 # Base case: 0 coins are needed to make amount 0 for i in range(1, amount + 1): for coin in coins: if i - coin >= 0: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] ! ...

Longest Increasing Subsequence

December 19, 2023

medium

dynamic programming, Greedy Algorithms

Problem # Find the longest increasing subsequence in a given sequence of numbers. Solution # def longest_increasing_subsequence(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) # Test the function with an example print(longest_increasing_subsequence([10, 22, 9, 33, 21, 50, 41, 60, 80])) In this code, the longest_increasing_subsequence function takes a list of integers as input and returns the length of the longest increasing subsequence in that list. ...