šŸ“Š Dynamic Programming Problems

Master memoization, tabulation, LCS, knapsack variations, and optimization problems

Coin Change - Minimum coins to make amount

Medium

Given coin denominations and a target amount, find minimum coins needed.
Input: coins = [1,2,5], amount = 11 ā†’ Output: 3 (5+5+1)

java

Longest Common Subsequence

Medium

Find the length of longest common subsequence of two strings.
Input: "abcde", "ace" ā†’ Output: 3 ("ace")

java

Word Break - Can string be segmented?

Medium

Given a string and dictionary, determine if string can be segmented into dictionary words.
Input: s = "leetcode", dict = ["leet","code"] ā†’ Output: true

java

Longest Increasing Subsequence

Medium

Find the length of longest strictly increasing subsequence.
Input: [10,9,2,5,3,7,101,18] ā†’ Output: 4 ([2,3,7,101])

java

Edit Distance (Levenshtein Distance)

Hard

Find minimum operations (insert, delete, replace) to convert word1 to word2.
Input: "horse", "ros" ā†’ Output: 3

java

0/1 Knapsack Problem

Medium

Given weights and values of items, find maximum value that fits in knapsack capacity.

java

House Robber - Maximum non-adjacent sum

Medium

Rob houses along a street without robbing two adjacent houses.
Input: [2,7,9,3,1] ā†’ Output: 12 (2+9+1)

java

Dynamic Programming Patterns