Recursive algorithms, while elegant in their formulation, can often suffer from significant performance drawbacks due to redundant computations. This is where dynamic programming techniques like memoization and tabulation come into play.
Memoization, a top-down approach, efficiently stores and reuses previously calculated results, mirroring the recursive structure while avoiding repeated calculations. This technique is generally easier to implement as it often closely resembles the original recursive solution, requiring primarily the addition of a caching mechanism.
Building upon the understanding of memoization, the bottom-up tabulation approach can be more readily grasped. Tabulation effectively reverses the order of calculations, systematically building up solutions from base cases, eliminating the need for explicit recursion. While initially more challenging to conceptualize, understanding memoization provides a strong foundation for comprehending the more efficient tabulation method, paving the way for further optimizations in dynamic programming.
Arrange balls
[Memoization] [Tabulation]
There are p, q and r balls. arrange balls in a straight line such that no two balls of the same type are adjacent.
Find Binomial coefficient
[Memoization] [Tabulation]
A binomial coefficient, n choose k formula, is also known as combinations formula, and is defined as
Find Nth Catalan Number
[Memoization] [Tabulation]
Find Nth Catalan Number (Tabulation)
Climbing stairs with 3 moves
[Memoization] [Tabulation]
There are n stairs, and a person standing at the bottom can climb either 1 stair, 2 stairs or 3 staris at a time, count the number of ways that a person can reach at the top.
Climbing stairs
[Memoization] [Tabulation]
There are n stairs, and a person standing at the bottom can climb either 1 stair or 2 stairs at a time, count the number of ways that a person can reach at the top.
Find minimum coins to make change
[Memoization] [Tabulation]
Given a list of coins[] of different denominations with infinite supply of each of the coins. Find the minimum number of coins required to make the given sum. If it's not possible to make a change, return -1.
Find number of way to make coin change
[Memoization] [Tabulation]
Given a list of coins[] representing different denominations, count all combinations of the coins to make a given value sum.
Find all subsequence combinations of a string
[Memoization] [Tabulation]
Given a string 'abc', find all distinct subsequence combinations of it.
Count number of derangements
[Memoization] [Tabulation]
Given a number n, find number of derangements in a set of n elements. A Derangement is a permutation with no element appears in its original position. For example, a derangement of [0, 1, 2] is [2, 0, 1].
Find all distinct subset sums of an array
[Memoization] [Tabulation]
Given a list of numbers, find all distinct sums that can be generated from the subsets of the given list and return them in increasing order.
Find Nth Fibonacci number
[Memoization] [Tabulation]
Given a positive integer n, find the nth Fibonacci number. Fibonacci numbers, when it starts from 0, are calculaed as F(n), where F(1) = 0, F(2) = 1, and F(n) = F(n-1) + F(n-2) for n > 2. Example of first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.
House robber
[Memoization] [Tabulation]
A robber wants to steal money from n houses built in a line, each of which contains some money in it. Given he can’t steal from two adjacent houses, find the maximum amount of money can be steal.
Find minimum of jumps to reach end
[Memoization] [Tabulation]
Imagine you're hopping along a number line. Each number on the line represents a position in a list of numbers. Each number on the line tells you the maximum distance you can hop forward from that position. Find the fewest hops needed to reach the very end of the number line, starting from the beginning. If a number is zero, you can't hop from that position at all.
0/1 Knapsack problem
[Memoization] [Tabulation]
Given list of N items where each item has some [weight, value] associated with it, put the items into a knapsack of capacity W to maximize the sum of values associated with the items. Break item is not allowed.
Unbounded knapsack
[Memoization] [Tabulation]
Given list of N items where each item has some [weight, value] associated with it, put the items into a knapsack of capacity W to maximize the sum of values associated with the items. Repetition of items is allowed.
Longest common increasing subsequence (LCS + LIS)
[Memoization] [Tabulation]
Given two arrays, a[] and b[], find the length of the longest common increasing subsequence(LCIS). LCIS refers to a subsequence that is present in both arrays and strictly increases.
Find longest common subsequence (LCS)
[Memoization] [Tabulation]
Given two strings, s1 and s2, find length of the longest common subsequence. Return 0 for nothing common.
Find longest common substring
[Memoization] [Tabulation]
Given two strings 's1' and 's2', find the length of the longest common substring.
Find longest increasing subsequence (LIS)
[Memoization] [Tabulation]
Given an array of size n, find the length of the longest increasing subsequence (LIS), in which the elements of the subsequence are sorted in increasing order.
Longest palindromic subsequence (LPS)
[Memoization] [Tabulation]
Given a string, find the length of the longest palindromic subsequence in it. For example, the length of the longest palindromic subsequence for 'bbbab' is 4 and the sequence is 'bbbb'.
Maximum size of square sub-matrix with all 1s
[Memoization] [Tabulation]
Given a binary matrix of size n * m, find out the maximum size of square sub-matrix with all 1s.
Min cost path
[Memoization] [Tabulation]
Given a 2d matrix cost[][], calculate the minimum cost path from (0, 0) to (m, n). Only move down, right and diagonally lower cells from a given cell is allowed.
Minimum insertions to form a palindrome
[Memoization] [Tabulation]
Given string str, find the minimum number of characters to be inserted to make it a palindrome.
Find the minimum number of edits
[Memoization] [Tabulation]
Given two strings s1 and s2 of lengths m and n, find the minimum number of edits (operations) to convert "s1" into "s2" using operations of insert, remove or replace of a char.
Number of unique BST with N keys
[Memoization] [Tabulation]
Given an integer n, count the total number of unique BSTs that can be made using values from 1 to n.
Maximize number segments of cutted in length x, y and z
[Memoization] [Tabulation]
Given a rod of length n, maximize the total number of segments can be cutted in length of x, y, and z.
Find number of ways paint a fence with n posts and k colors
[Memoization] [Tabulation]
Find out the number of ways of painting a fence with n posts and k colors so that not more than two consecutive posts have the same color.
Partition a set into two subsets of equal sum
[Memoization] [Tabulation]
Given a list of numbers, check if it can be partitioned into two parts such that the sum of elements in both parts is the same.
Pascal's Triangle
[Memoization] [Tabulation]
Given an integer n, find the first n rows of Pascal's triangle.
Regular expression wildcard pattern matching
[Memoization] [Tabulation]
Given a text and a pattern, test if pattern matches text. Both text and pattern consist of only lowercase alphabets while pattern also consists special characters of "." and "\*". "." matches any single character and **"\*" matches zero or more of the preceding character**.
Find number of permutation with K inversions
[Memoization] [Tabulation]
Given two numbers n and k, find how many permutations of the first n number have exactly k inversion. An inversion is defined as a[i] > a[j] for i < j.
Print maximum number of A’s using given four keys
[Memoization] [Tabulation]
Give a special keyboard with the following four keys Key 1: Prints 'A' on screen, Key 2: Select screen, Key 3: Copy selection, Key 4: Paste selection on screen after what has already been printed. Given a number N times (with the above four keys), write a program to produce maximum numbers of A's.
Stacking box
[Memoization] [Tabulation]
Given a list of three values, height, width and length, create a stack of boxes that is as tall as possible. A box can be stacked on top of another box if dimensions of its 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. A box can stack in any orientation and multiple instances of the same type of box is allowed.
Subsequence with difference of 1
[Memoization] [Tabulation]
Given a list of numbers, find the longest subsequence such that the absolute difference between adjacent elements is 1.
Subset sum
[Memoization] [Tabulation]
Given a list[] of non-negative integers and a value sum, check if there is a subset of the given list whose sum is equal to the given number.
Maximize total tips
[Memoization] [Tabulation]
A restaurant received n orders. The two waiters A and B in the restaurant change different amount of tip, listed in A[] and B[], for an order. Given A can handle max X order and B can handle max Y order, Find out the maximum possible amount of total tips to handle all the orders.
Find Nth Tribonacci number
[Memoization] [Tabulation]
Given a positive integer n, find the nth Tribonacci number. Tribonacci numbers, when it starts from 0, are calculaed as T(n), where T(1) = T(2) = 0, T(3) = 1, and T(n) = T(n-1) + T(n-2) + T(n-3) for n > 3. Example of first few Tribonacci numbers are 0, 0, 1, 1, 2, 4, 7, 13, 24, 44.
Count unique paths in matrix from top left to bottom right
[Memoization] [Tabulation]
Given m x n matrix, count of all unique possible paths from top left to the bottom right. From each cell, only move right or down is allowed.
Weighted interval job scheduling
[Memoization] [Tabulation]
Given n jobs where every job has the start time, finish time and profit associated. Find the maximum profit in scheduling jobs such that no two jobs overlap.
Word Break
[Memoization] [Tabulation]
Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.