What is Dynamic Programming?

Introduction

0/1 Knapsack

Solution: 0/1 Knapsack

Equal Subset Sum Partition

Solution: Equal Subset Sum Partition

Subset Sum

Solution: Subset Sum

Minimum Subset Sum Difference

Solution: Minimum Subset Sum Difference

Count of Subset Sum

Solution: Count of Subset Sum

Target Sum

Solution: Target Sum

Pattern 1: 0/1 Knapsack

Unbounded Knapsack

Solution: Unbounded Knapsack

Rod Cutting

Solution: Rod Cutting

Coin Change

Solution: Coin Change

Minimum Coin Change

Solution: Minimum Coin Change 

Maximum Ribbon Cut

Solution: Maximum Ribbon Cut

Pattern 2: Unbounded Knapsack

Fibonacci numbers

Solution: Fibonacci numbers

Staircase

Solution: Staircase

Number factors

Solution: Number factors

Minimum jumps to reach the end

Solution: Minimum jumps to reach the end

Minimum jumps with fee

Solution: Minimum jumps with fee

House thief

Solution: House thief

Pattern 3: Fibonacci Numbers

Longest Palindromic Subsequence

Solution: Longest Palindromic Subsequence

Longest Palindromic Substring

Solution: Longest Palindromic Substring

Count of Palindromic Substrings

Solution: Count of Palindromic Substrings

Minimum Deletions in a String to make it a Palindrome

Solution: Minimum Deletions in a String to make it a Palindrome

Palindromic Partitioning

Solution: Palindromic Partitioning

Pattern 4: Palindromic Subsequence

Longest Common Substring

Solution: Longest Common Substring

Longest Common Subsequence

Solution: Longest Common Subsequence

Minimum Deletions & Insertions to Transform a String into another

Solution: Minimum Deletions & Insertions to Transform a String into another

Longest Increasing Subsequence

Solution: Longest Increasing Subsequence

Maximum Sum Increasing Subsequence

Solution: Maximum Sum Increasing Subsequence

Shortest Common Super-sequence

Solution: Shortest Common Super-sequence

Minimum Deletions to Make a Sequence Sorted

Solution: Minimum Deletions to Make a Sequence Sorted

Longest Repeating Subsequence

Solution: Longest Repeating Subsequence

Subsequence Pattern Matching

Solution: Subsequence Pattern Matching

Longest Bitonic Subsequence

Solution: Longest Bitonic Subsequence

Longest Alternating Subsequence

Solution: Longest Alternating Subsequence

Edit Distance

Solution: Edit Distance

Strings Interleaving

Solution: Strings Interleaving

Pattern 5: Longest Common Substring

Contact Us

Appendix

Grokking Dynamic Programming Patterns for Coding Interviews

## Introduction

Given an infinite supply of ‘n’ coin denominations and a total money amount, we are asked to find the minimum number of coins needed to make up that amount.

**Example 1:**
```
Denominations: {1,2,3}
Total amount: 5
Output: 2
Explanation: We need a minimum of two coins {2,3} to make a total of '5'
```
**Example 2:**
```
Denominations: {1,2,3}
Total amount: 11
Output: 4
Explanation: We need a minimum of four coins {2,3,3,3} to make a total of '11'
```

