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

## Problem Statement
Given a number sequence, find the length of its Longest Alternating Subsequence (LAS). A subsequence is considered alternating if its elements are in alternating order. 

A three element sequence (a1, a2, a3) will be an alternating sequence if its elements hold one of the following conditions: 
```
{a1 > a2 < a3 } or { a1 < a2 > a3}. 
```

**Example 1:**
```
Input: {1,2,3,4}
Output: 2
Explanation: There are many LAS: {1,2}, {3,4}, {1,3}, {1,4}
```
**Example 2:**
```
Input: {3,2,1,4}
Output: 3
Explanation: The LAS are {3,2,4} and {2,1,4}.
```

**Example 3:**
```