# Introduction To

Dynamic Programming Algorithm is an algorithm technique used primarily for optimizing problems, where we wish to find the “best” way of doing something. It is both a mathematical optimization method and a computer programming method.

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead. This is why merge sort and quick sort are not classified as dynamic programming problems.

The technique was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.

# Course Structure

## Basic Concepts

## Advanced Concepts

## Basic Problems

- Ugly Numbers
- Permutation Coefficient
- Tiling Problem
- Gold Mine Problem
- Coin Change | DP-7
- Friends Pairing Problem
- Subset Sum Problem | DP-25
- Subset Sum Problem in O(sum) space
- Subset with sum divisible by m
- Perfect Sum Problem (Print all subsets with given sum)
- Cutting a Rod | DP-13
- Tiling with Dominoes
- Painting Fence Algorithm
- Newman–Shanks–Williams prime
- Assembly Line Scheduling | DP-34
- Golomb sequence
- Find maximum length Snake sequence
- Print n terms of Newman-Conway Sequence
- Print Fibonacci sequence using 2 variables
- Print Fibonacci Series in reverse order
- Count even length binary sequences with same sum of first and second half bits
- Sequences of given length where every element is more than or equal to twice of previous
- Longest Common Subsequence | DP-4
- Longest Repeated Subsequence
- Longest Increasing Subsequence | DP-3
- A Space Optimized Solution of LCS
- LCS (Longest Common Subsequence) of three strings
- Maximum sum Bi-tonic Sub-sequence
- Maximum Sum Increasing Subsequence | DP-14
- Maximum product of an increasing subsequence
- Count all subsequences having product less than K
- Maximum subsequence sum such that no three are consecutive
- Longest subsequence such that difference between adjacents is one
- Maximum length subsequence with difference between adjacent elements as either 0 or 1
- Maximum sum increasing subsequence from a prefix and a given element after prefix is must
- Maximum Length Chain of Pairs | DP-20
- Print Maximum Length Chain of Pairs
- Path with maximum average value
- Maximum games played by winner
- Maximum path sum in a triangle.
- Minimum Sum Path in a Triangle
- Maximum sum of a path in a Right Number Triangle
- Size of The Subarray With Maximum Sum
- Maximum sum of pairs with specific difference
- Maximum size square sub-matrix with all 1s
- Maximum number of segments of lengths a, b and c
- Recursively break a number in 3 parts to get maximum sum
- Maximum value with the choice of either dividing or considering as it is
- Maximum weight path ending at any element of last row in a matrix
- Maximum sum in a 2 x n grid such that no two elements are adjacent
- Maximum difference of zeros and ones in binary string | Set 2 (O(n) time)
- Maximum path sum for each position with jumps under divisibility condition
- Maximize the sum of selected numbers from an array to make it empty
- Maximum subarray sum in an array created after repeated concatenation
- Maximum path sum that starting with any cell of 0-th row and ending with any cell of (N-1)-th row
- Min Cost Path | DP-6
- Minimum number of jumps to reach end
- Minimum cost to fill given weight in a bag
- Minimum sum of multiplications of n numbers
- Minimum removals from array to make max – min <= K
- Minimum steps to minimize n as per given condition
- Edit Distance | DP-5
- Minimum time to write characters using insert, delete and copy operation
- Longest Common Substring | DP-29
- Longest Common Substring (Space optimized DP solution)
- Sum of all substrings of a string representing a number | Set 1
- Find number of endless points
- Find n-th element from Stern’s Diatomic Series
- Find maximum possible stolen value from houses
- Count number of ways to reach a given score in a game
- Count ways to reach the nth stair using step 1, 2 or 3
- Count of different ways to express N as the sum of 1, 3 and 4
- Count ways to build street under given constraints
- Count Balanced Binary Trees of Height h
- Counting pairs when a person can form pair with at most one
- Counts paths from a point to reach Origin
- Count number of ways to cover a distance
- Count of arrays having consecutive element with different values
- Count the number of ways to tile the floor of size n x m using 1 x m size tiles
- Count all possible paths from top left to bottom right of a mXn matrix
- Count number of ways to fill a “n x 4” grid using “1 x 4” tiles
- Smallest sum contiguous subarray
- Size of array after repeated deletion of LIS
- Remove array end element to maximize the sum of product
- Convert to Strictly increasing integer array with minimum changes
- Longest alternating (positive and negative) subarray starting at every index
- Ways to sum to N using array elements with repetition allowed
- Unique paths in a Grid with Obstacles
- Number of n-digits non-decreasing integers
- Number of ways to arrange N items under given constraints
- Probability of reaching a point with 2 or 3 steps at a time
- Value of continuous floor function : F(x) = F(floor(x/2)) + x
- Number of decimal numbers of length k, that are strict monotone
- Different ways to sum n using numbers greater than or equal to m

## Intermediate Problems

- Lobb Number
- Eulerian Number
- Delannoy Number
- Entringer Number
- Jacobsthal and Jacobsthal-Lucas numbers
- Super Ugly Number (Number whose prime factors are in given set)
- 0-1 Knapsack Problem | DP-10
- Printing Items in 0/1 Knapsack
- Unbounded Knapsack (Repetition of items allowed)
- Temple Offerings
- Egg Dropping Puzzle | DP-11
- Dice Throw | DP-30
- Word Break Problem | DP-32
- Vertex Cover Problem | Set 2 (Dynamic Programming Solution for Tree)
- Tile Stacking Problem
- Box Stacking Problem | DP-22
- Highway Billboard Problem
- Largest Independent Set Problem | DP-26
- Partition problem | DP-18
- Print equal sum sets of array (Partition problem) | Set 1
- Print equal sum sets of array (Partition Problem) | Set 2
- Dynamic Programming | High-effort vs. Low-effort Tasks Problem
- Longest Bitonic Subsequence | DP-15
- Printing Longest Bitonic Subsequence
- Longest Palindromic Subsequence | DP-12
- Print Longest Palindromic Subsequence
- Longest palindrome subsequence with O(n) space
- Count All Palindromic Subsequence in a given String
- Longest Palindromic Substring | Set 1
- Count All Palindrome Sub-Strings in a String | Set 1
- Number of palindromic subsequences of length k where k <= 3
- Count of Palindromic substrings in an Index range
- Shortest Common Supersequence
- Maximum sum alternating subsequence
- Longest alternating subsequence
- Shortest Uncommon Subsequence
- Longest Repeating Subsequence
- Count Distinct Subsequences
- Longest Common Increasing Subsequence (LCS + LIS)
- Variations of LIS | DP-21
- LCS formed by consecutive segments of at least length K
- Printing Maximum Sum Increasing Subsequence
- Longest Increasing Odd Even Subsequence
- Count number of increasing subsequences of size k
- Printing longest Increasing consecutive subsequence
- Construction of Longest Increasing Subsequence using Dynamic Programming
- Longest Zig-Zag Subsequence
- Largest sum Zigzag sequence in a matrix
- Find all distinct subset (or subsequence) sums of an array
- Print all longest common sub-sequences in lexicographical order
- Printing Longest Common Subsequence | Set 2 (Printing All)
- Length of Longest Balanced Subsequence
- Non-decreasing subsequence of size k with minimum sum
- Longest Common Subsequence with at most k changes allowed
- Weighted Job Scheduling
- Weighted Job Scheduling | Set 2 (Using LIS)
- Weighted Job Scheduling in O(n Log n) time
- Number of paths with exactly k coins
- Find minimum number of coins that make a given value
- Collect maximum coins before hitting a dead end
- Coin game winner where every player has three choices
- Probability of getting at least K heads in N tosses of Coins
- Count all increasing subsequences
- Count number of paths with at-most k turns
- Count possible ways to construct buildings
- Count number of ways to jump to reach end
- Count number of ways to reach destination in a Maze
- Count all triplets whose sum is equal to a perfect cube
- Count number of binary strings without consecutive 1’s
- Count number of subsets having a particular XOR value
- Count number of ways to partition a set into k subsets
- Count of n digit numbers whose sum of digits equals to given sum
- Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique cap to every person)
- Count binary strings with k times appearing adjacent two set bits
- Count of strings that can be formed using a, b and c under given constraints
- Count total number of N digit numbers such that the difference between sum of even and odd digits is 1
- Maximum Product Cutting | DP-36
- Maximum profit from sale of wines
- Maximum size subset with given sum
- Maximum difference of zeros and ones in binary string
- Maximum and Minimum Values of an Algebraic Expression
- Maximum average sum partition of an array
- Maximize array elements upto given number
- Maximum subarray sum in O(n) using prefix sum
- Maximum sum subarray removing at most one element
- K maximum sums of non-overlapping contiguous sub-arrays
- Maximum Product Subarray | Added negative product case
- Find maximum sum array of length less than or equal to m
- Find Maximum dot product of two arrays with insertion of 0’s
- Choose maximum weight with given weight and value ratio
- Maximum sum subsequence with at-least k distant elements
- Maximum profit by buying and selling a share at most twice
- Maximum sum path in a matrix from top to bottom
- Maximum decimal value path in a binary matrix
- Finding the maximum square sub-matrix with all equal elements
- Maximum points collected by two persons allowed to meet once
- Maximum number of trailing zeros in the product of the subsets of size k
- Minimum Sum Path In 3-D Array
- Minimum insertions to sort an array
- Minimum sum submatrix in a given 2D array
- Minimum Initial Points to Reach Destination
- Minimum Cost To Make Two Strings Identical
- Paper Cut into Minimum Number of Squares | Set 2
- Minimum and Maximum values of an expression with * and +
- Minimum insertions to form a palindrome | DP-28
- Minimum number of deletions to make a string palindrome
- Minimum number of deletions to make a string palindrome | Set 2
- Minimum jumps to reach last building in a matrix
- Sub-tree with minimum color difference in a 2-coloured tree
- Minimum number of deletions to make a sorted sequence
- Minimum number of squares whose sum equals to given number n
- Remove minimum elements from either side such that 2*min becomes more than max
- Minimal moves to form a string by adding characters or appending string itself
- Minimum steps to delete a string after repeated deletion of palindrome substrings
- Clustering/Partitioning an array such that sum of square differences is minimum
- Minimum sum subsequence such that at least one of every four consecutive elements is picked
- Minimum cost to make Longest Common Subsequence of length k
- Minimum cost to make two strings identical by deleting the digits
- Minimum time to finish tasks without skipping two consecutive
- Minimum cells required to reach destination with jumps equal to cell values
- Minimum number of deletions and insertions to transform one string into another
- Find minimum adjustment cost of an array
- Find if string is K-Palindrome or not | Set 1
- Find if string is K-Palindrome or not | Set 2
- Find Jobs involved in Weighted Job Scheduling
- Find the Longest Increasing Subsequence in Circular manner
- Find the longest path in a matrix with given constraints
- Find minimum sum such that one of every three consecutive elements is taken
- Find number of times a string occurs as a subsequence in given string
- Find length of the longest consecutive path from a given starting character
- Find length of longest subsequence of one string which is substring of another string
- Find longest bitonic sequence such that increasing and decreasing parts are from two different arrays
- WildCard pattern matching having three symbols ( * , + , ? )
- Check if any valid sequence is divisible by M
- Check for possible path in 2D matrix
- Check if possible to cross the matrix with given power
- Check if it is possible to transform one string to another
- Optimal Binary Search Tree | DP-24
- Number of permutation with K inversions
- Largest divisible pairs subset
- Compute sum of digits in all numbers from 1 to n
- Total number of non-decreasing numbers with n digits
- Dynamic Programming | Building Bridges
- Longest Increasing Path in Matrix
- Prefix Sum of Matrix (Or 2D Array)
- Number of n digit stepping numbers
- Number of substrings divisible by 8 but not by 3
- Number of ordered pairs such that (Ai & Aj) = 0
- Number of ways to form a heap with n distinct integers
- Ways to write n as sum of two or more positive integers
- Modify array to maximize sum of adjacent differences
- Sum of products of all combination taken (1 to n) at a time
- Maximize the binary matrix by filpping submatrix once
- Length of the longest substring without repeating characters
- Longest Even Length Substring such that Sum of First and Second Half is same
- Ways to arrange Balls such that adjacent balls are of different types
- Ways of transforming one string to other by removing 0 or more characters
- Balanced expressions such that given positions have opening brackets
- Longest alternating sub-array starting from every index in a Binary Array
- Partition a set into two subsets such that the difference of subset sums is minimum
- Pyramid form (increasing then decreasing) consecutive array using reduce operations

## Hard Problems

- Palindrome Partitioning | DP-17
- Word Wrap Problem | DP-19
- Mobile Numeric Keypad Problem
- The painter’s partition problem
- Boolean Parenthesization Problem | DP-37
- Program for Bridge and Torch problem
- A Space Optimized DP solution for 0-1 Knapsack Problem
- Matrix Chain Multiplication | DP-8
- Printing brackets in Matrix Chain Multiplication Problem
- Number of palindromic paths in a matrix
- Largest rectangular sub-matrix whose sum is 0
- Largest rectangular sub-matrix having sum divisible by k
- Largest area rectangular sub-matrix with equal number of 1’s and 0’s
- Maximum sum bitonic subarray
- Maximum sum rectangle in a 2D matrix | DP-27
- Maximum Subarray Sum Excluding Certain Elements
- Maximum weight transformation of a given string
- Collect maximum points in a grid using two traversals
- K maximum sums of overlapping contiguous sub-arrays
- How to print maximum number of A’s using given four keys
- Maximize arr[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l
- Maximum profit by buying and selling a share at most k times
- Maximum points from top left of matrix to bottom right and return back
- Check whether row or column swaps produce maximum size binary sub-matrix with all 1s
- Minimum cost to sort strings using reversal operations of different costs
- Find minimum possible size of array with given rules for removing elements
- Minimum number of elements which are not part of Increasing or decreasing subsequence in array
- Count ways to increase LCS length of two strings by one
- Count of AP (Arithmetic Progression) Subsequences in an array
- Count of arrays in which all adjacent elements are such that one of them divide the another
- Number of NGEs to the right
- Longest Arithmetic Progression | DP-35
- Longest Geometric Progression
- Dynamic Programming on Trees | Set-1
- Dynamic Programming on Trees | Set 2
- All ways to add parenthesis for evaluation
- Shortest possible combination of two strings
- Check if all people can vote on two machines
- Find if a string is interleaved of two other strings | DP-33
- Longest repeating and non-overlapping substring
- Probability of Knight to remain in the chessboard
- Number of subsequences of the form a^i b^j c^k
- Number of subsequences in a string divisible by n
- Printing Shortest Common Supersequence
- Smallest length string with repeated replacement of two distinct adjacent
- Number of ways to insert a character to increase the LCS by one
- Traversal of tree with k jumps allowed between nodes of same height
- Find all combinations of k-bit numbers with n bits set where 1 <= n <= k in sorted order