You need to login before you can make any post submission.
It is an algorithmic paradigm that solves a given complex problem by:
Following are the two main properties of a problem that suggests that the given problem can be solved using Dynamic programming.
Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems.
Dynamic Programming is mainly used when solutions of same subproblems are needed again and again.
In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed.
Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again.
Binary Search is broken down into subproblems but it doesn’t have common subproblems, so no sense to store the solutions.
There are following two different ways to store the values so that these values can be reused:
def fib_memoization_top_down(n, lookup):
if(n == 0 or n == 1):
lookup[n] = n
if(lookup[n] is None):
lookup[n] = fib_memoization_top_down(n-1, lookup) + fib_memoization_top_down(n-2, lookup)
return lookup[n]
print("Fibonacci: DP(Top_Down/Memoization) Approach Example-1:")
print(fib_memoization_top_down(5, [None]*(6)))
print("Fibonacci: DP(Top_Down/Memoization) Approach Example-2:")
print(fib_memoization_top_down(34, [None]*(35)))
Output:
def fib_tabulation_bottom_up(n):
table = [0]*(n+1)
table[1] = 1
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
print("Fibonacci: DP(Bottom_Up/Tabulation) Approach Example-1:")
print(fib_tabulation_bottom_up(5))
print("Fibonacci: DP(Bottom_Up/Tabulation) Approach Example-2:")
print(fib_tabulation_bottom_up(34))
Output:
A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.
Example:- The Shortest Path problem has following optimal substructure property:
But the Longest Path problem i.e. longest simple path (path without cycle) between two nodes doesn’t have the Optimal Substructure property.
Find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.
def maximum_sum_subarray_kadane(arr):
n = len(arr)
max_so_far = arr[0]
max_ending_here = arr[0]
start = 0; end = 0; s = 0;
for i in range(1, n):
max_ending_here += arr[i]
if(max_so_far < max_ending_here):
max_so_far = max_ending_here
start = s
end = i
if(max_ending_here < 0):
max_ending_here = 0
s = i+1
return (max_so_far, arr[start:end+1])
print("Example-1: maximum_sum_subarray_kadane(arr)")
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
max_sum, subarray = maximum_sum_subarray_kadane(arr)
print("Max: {} and Subarray: {}".format(max_sum, subarray))
print("\nExample-2: maximum_sum_subarray_kadane(arr)")
arr = [-13, -3, -25, -20, -3, -16, -23, -12, -5, -22, -15, -4, -7]
ax_sum, subarray = maximum_sum_subarray_kadane(arr)
print("Max: {} and Subarray: {}".format(max_sum, subarray))
Output:
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Example:
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 11
Output: True //There is a subset (4, 5, 2) with sum 11.
def is_subset_sum_recursive(given_set, n, given_sum):
if(given_sum==0):
return True
if(n==0 and given_sum != 0):
return False
return is_subset_sum_recursive(given_set, n-1, given_sum) or
is_subset_sum_recursive(given_set, n-1, given_sum-given_set[n-1])
print("Example-1: is_subset_sum_recursive(given_set, n, given_sum)")
given_set = [1, 3, 9, 2]
print(is_subset_sum_recursive(given_set, 4, 5))
print("Example-2: is_subset_sum_recursive(given_set, n, given_sum)")
given_set = [3, 34, 4, 12, 5, 2]
print(is_subset_sum_recursive(given_set, 6, 11))
print("Example-3: is_subset_sum_recursive(given_set, n, given_sum)")
given_set = [3, 34, 4, 12, 5, 2]
print(is_subset_sum_recursive(given_set, 6, 13))
Output
table[i][j]
will be true if there is a subset of set[0..j-1] with sum equal to i., otherwise false.[sum][n]
.def is_subset_sum_dp(given_set, n, given_sum):
table = [[False]*(given_sum+1) for i in range(n+1)]
# Sum = 0 can be achieved by any subset by taking an empty set
for i in range(n+1):
table[i][0] = True
# With empty set all the sum will be False except sum=0
for i in range(1, given_sum+1):
table[0][i] = False
# Now fill the rest of table
for i in range(1, n+1):
for j in range(1, given_sum+1):
# If earlier (before adding this number in set) sum was possible,
# the now also it will be possible
if(table[i-1][j] == True):
table[i][j] = True
# If earlier not possible check if current_sum-current_number was possible earlier,
# if it was then we are done.
elif(j-given_set[i-1]>=0 and table[i-1][j-given_set[i-1]] == True):
table[i][j] = True
# If above 2 cases is not there, then False
else:
table[i][j] = False
return table[n][given_sum]
print("Example-1: is_subset_sum_dp(given_set, n, given_sum)")
given_set = [1, 3, 9, 2]
print(is_subset_sum_dp(given_set, 4, 5))
print("Example-2: is_subset_sum_dp(given_set, n, given_sum)")
given_set = [3, 34, 4, 12, 5, 2]
print(is_subset_sum_dp(given_set, 6, 11))
print("Example-3: is_subset_sum_dp(given_set, n, given_sum)")
given_set = [3, 34, 4, 12, 5, 2]
print(is_subset_sum_dp(given_set, 6, 13))
Output:
Given an array of integers where each element represents the max number of steps that can be made forward from that element.
Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element).
If an element is 0, then cannot move through that element.
Example:
Input: arr[] = {2, 3, 1, 2, 3, 4, 2, 0, 8, 1}
Output: 4 (2-> 3-> 2-> 4-> 1)
import sys
def min_jump_to_reach_end_recursive(arr, start, end):
# Base case: when start position and end position are same
if (start == end):
return 0
# When nothing is reachable from the given position
if (arr[start] == 0):
return sys.maxsize
# Just check where you can reach from start and then call min_jump from there
min_jumps = sys.maxsize
for i in range(1, arr[start]+1):
next_start = start+i
if(next_start < n):
jumps = 1 + min_jump_to_reach_end_recursive(arr, next_start, end)
if (jumps < min_jumps):
min_jumps = jumps
return min_jumps
print("Min Jump Recursive Example-1: min_jump_to_reach_end_recursive(arr, start, end)")
arr = [2, 3, 1, 2, 3, 4, 2, 0, 8, 1]
n = len(arr)
jumps = min_jump_to_reach_end_recursive(arr, 0, n-1)
if(jumps == sys.maxsize):
print("Unreachable")
else:
print("Jumps: {}".format(jumps))
print("\nMin Jump Recursive Example-2: min_jump_to_reach_end_recursive(arr, start, end)")
arr = [2, 3, 1, 2, 3, 2, 1, 0, 8, 1]
n = len(arr)
jumps = min_jump_to_reach_end_recursive(arr, 0, n-1)
if(jumps == sys.maxsize):
print("Unreachable")
else:
print("Jumps: {}".format(jumps))
Output:
def min_jump_to_reach_end_DP(arr):
n = len(arr)
# Initialize jumps_required as "infinity" for every element
jumps_required = [sys.maxsize]*n
actual_jump = [0]*n
# First element is reachable by 0 jumps
jumps_required[0] = 0
for i in range(1, n):
for j in range(i):
# Check if from j we can reach i or not??
# If j + arr[j] >= i : then we can reach i
if(j+arr[j] >= i):
# If i is reachable from j in lesser jumps than earlier update the jumps to reach i
# Update the actual jump table also
if(jumps_required[j]+1 < jumps_required[i]):
jumps_required[i] = jumps_required[j]+1
actual_jump[i] = j
# Now print number of jumps and actual jump
if(jumps_required[n-1] == sys.maxsize):
print("Unreachable")
else:
print("Jumps: {}".format(jumps_required[n-1]))
k = n-1
print("Actual Jumps: end", end="")
while(k>0):
print("<--{}".format(actual_jump[k]), end="")
k = actual_jump[k]
print()
print("Min Jump DP Example-1: min_jump_to_reach_end_DP(arr)")
arr = [2, 3, 1, 2, 3, 4, 2, 0, 8, 1]
min_jump_to_reach_end_DP(arr)
print("\nMin Jump DP Example-2: min_jump_to_reach_end_DP(arr)")
arr = [2, 3, 1, 2, 3, 2, 1, 0, 8, 1]
min_jump_to_reach_end_DP(arr)
Output:
There exists a O(n) solution to be discussed later.
Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins.
How many unique ways can we make the change? The order of coins doesn’t matter.
Example:
Input: N = 5 and S = {1, 2, 5} Output: 4 {1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5}.
Input: N = 10 and S = {2, 5, 3, 6} Output: 5 {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}
def coin_change_unique_ways_recursive(coins, N):
m = len(coins)
# If N is less than 0 then no solution exists
if (N < 0):
return 0
# If N is 0 then 1 solution : Don't include any coin
if (N == 0):
return 1
# If no coins, no solution exist
if (m == 0):
return 0
# Answer is sum of solutions (i)including first coin (ii) excluding first coin
return coin_change_unique_ways_recursive(coins, N-coins[0]) +
coin_change_unique_ways_recursive(coins[1:], N)
print("Example-1: coin_change_unique_ways_recursive(coins, N)")
coins = [1, 2, 5]
print(coin_change_unique_ways_recursive(coins, 5))
print("Example-2: coin_change_unique_ways_recursive(coins, N)")
coins = [2, 5, 3, 6]
print(coin_change_unique_ways_recursive(coins, 10))
Output:
def coin_change_unique_ways_DP(coins, N):
m = len(coins)
table = [[0]*(N+1) for i in range(m+1)]
# when N=0, 1 solution:- Don't include anyone --- Fill first column
for i in range(m+1):
table[i][0] = 1
# When No coins or m = 0 :- No solution possible ---- Fill first row
# Line can be omitted as table is initialized with 0, just for better understanding
for j in range(1, N+1):
table[0][j] = 0
# Fill rest of the table
# table[i][j] = table[i-1][j] + table[i][j-coins[i-1]]
# table[i][j] = (Not including current coin) + (Including current coin)
for i in range(1, m+1):
for j in range(1, N+1):
# Can't include current coin
if(j-coins[i-1] < 0):
table[i][j] = table[i-1][j]
else:
table[i][j] = table[i-1][j] + table[i][j-coins[i-1]] # Include current coin
return table[m][N]
print("Example-1: coin_change_unique_ways_DP(coins, N)")
coins = [1, 2, 5]
print(coin_change_unique_ways_DP(coins, 5))
print("Example-2: coin_change_unique_ways_DP(coins, N)")
coins = [2, 5, 3, 6]
print(coin_change_unique_ways_DP(coins, 10))
Output:
Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, .. , Cm} valued coins.
What is the minimum number of coins to make the change?
Example:
Input: N = 11 and S = {1, 5, 6, 8} Output: 2 {5, 6}
import sys
def coin_change_min_coins_recursive(coins, N):
m = len(coins)
# if N==0, No coins needed
if(N == 0):
return 0
# if N < 0, return MAX and also when no coins
if(N < 0 or m == 0):
return sys.maxsize
# Now find minimum no. of coins by including every coin one by one
min_coins = sys.maxsize
for i in range(m):
min_coins = min(1 + coin_change_min_coins_recursive(coins, N-coins[i]), min_coins)
return min_coins
print("Example-1: coin_change_min_coins_recursive(coins, N)")
coins = [1, 5, 6, 8]
print(coin_change_min_coins_recursive(coins, 11))
print("Example-2: coin_change_min_coins_recursive(coins, N)")
coins = [2, 5, 7]
print(coin_change_min_coins_recursive(coins, 3))
Output:
def coin_change_min_coins_DP(coins, N):
m = len(coins)
table = [[sys.maxsize]*(N+1) for i in range(m+1)]
# If N = 0 then coins required = 0 --- Fill first column
for i in range(m+1):
table[i][0] = 0
# If coins = 0 then coins required = INFINITY --- Fill first column
# This line can be omitted, just for understanding as we have initialized with infinity
for j in range(1, N+1):
table[0][j] = sys.maxsize
# Now fill the table
for i in range(1, m+1):
for j in range(1, N+1):
if(j-coins[i-1] < 0):
table[i][j] = table[i-1][j]
else:
table[i][j] = min(1+table[i][j-coins[i-1]], table[i-1][j])
return table[m][N]
print("Example-1: coin_change_min_coins_DP(coins, N)")
coins = [1, 5, 6, 8]
print(coin_change_min_coins_DP(coins, 11))
print("Example-2: coin_change_min_coins_DP(coins, N)")
coins = [2, 5, 7]
print(coin_change_min_coins_DP(coins, 3))
Output:
There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time.
Count the number of ways, the person can reach the top.
Examples:
Input: n = 1 Output: 1 There is only one way to climb 1 stair
Input: n = 2 Output: 2 There are two ways: (1, 1) and (2)
Input: n = 3 Output: 3 (1, 1, 1), (2, 1), (1, 2)
Input: n = 4 Output: 5 (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2)
If the total_ways(N) is the total count of ways to reach Nth stair.
total_ways(N) = total_ways(N-1) + total_ways(N-2)
total_ways(N) = 1 step taken + 2 steps taken
Problem can be solved using fibonacci problem strategy.
def count_ways_to_nth_stair(N):
# If N <= 0 :- 0 or less stairs no ways to reach Nth stair
if(N <= 0):
return 0
# If N == 1 :- only 1 way walk 1 stair
# If N == 2 :- 2 ways ({1,1}, {2})
if (N == 1 or N == 2):
return N
# Else return no. of ways of reaching Nth stair by taking 1 step and 2 steps at once
return count_ways_to_nth_stair(N-1) + count_ways_to_nth_stair(N-2)
print("Example-1: count_ways_to_nth_stair(3)")
print(count_ways_to_nth_stair(3))
print("Example-2: count_ways_to_nth_stair(4)")
print(count_ways_to_nth_stair(4))
Output:
If max 2 stairs can be climbed at once, then this problem can be solved by FIBONACCI problem strategy.
If max m stairs can be climbed at once, then this problem can be solved by MIN_COINS problem strategy.
Given a “2 x n” board and “2 x 1” tiles, count the number of ways to tile the given board using the 2 x 1 tiles.
A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.
Example:
Input n = 3 Output: 3
Explanation:
We need 3 tiles to tile the board of size 2 x 3.
We can tile the board using following ways
1) Place all 3 tiles vertically.
2) Place first tile vertically and remaining 2 tiles horizontally.
3) Place first 2 tiles horizontally and remaining tiles vertically
Input n = 4 Output: 5
Explanation:
For a 2 x 4 board, there are 5 ways
1) All 4 vertical
2) All 4 horizontal
3) First 2 vertical, remaining 2 horizontal
4) First 2 horizontal, remaining 2 vertical
5) Corner 2 vertical, middle 2 horizontal
Let total_ways(N) be the count of ways to place tiles on a “2 x n” grid, we have following two ways to place first tile.
total_ways(N) = total_ways(N-1) + total_ways(N-2)
total_ways(N) = 1 step taken + 2 steps taken
This problem like the previous can again be solved using fibonacci problem strategy.
def count_tiling_ways(N):
# If N <= 0 No way to put any tile
if(N <= 0):
return 0
# If N == 1 :- only 1 way put horizontal
# If N == 2 :- 2 ways either both horizontal or both vertical
if (N == 1 or N == 2):
return N
# Else return no. of ways of filling board by first putting 1 tile vertically or 2 tile horizontally
return count_tiling_ways(N-1) + count_tiling_ways(N-2)
print("Example-1: count_tiling_ways(3)")
print(count_tiling_ways(3))
print("Example-2: count_tiling_ways(4)")
print(count_tiling_ways(4))
Output: