There are two approaches to solve any DP problem:
- Tabulation - Bottom up approach
- The problem is solved in the direction of solving the base cases to the main problem
- Memoization - Top down approach
- The problem is solved in the direction of the main problem to the base cases.
Problem Contest: https://atcoder.jp/contests/dp
1D Dynamic Programming
How to Identify a DP Problem?
- If problem asks following:
- Count total number of ways
- Given multiple ways of doing a task, which way will give the minimum or the maximum output.
- First try to solve problem using the recursion and then convert it to DP
Steps to solve any DP problem:
- Try to represent problem in terms of index
- Try all possible choices/ways at every index according to the problem statement.
- If the question states
- Count all the ways - return sum of all choices/ways.
- Find maximum/minimum- return the choice/way with maximum/minimum output.
Problems
Climbing Stairs
Frog Jump
Problem Statement:
- Link: https://takeuforward.org/data-structure/dynamic-programming-frog-jump-dp-3/
- Given a number of stairs and a frog, the frog wants to climb from the 0th stair to the (N-1)th stair. At a time the frog can climb either one or two steps.
- A height[N] array is also given. Whenever the frog jumps from a stair i to stair j, the energy consumed in the jump is abs(height[i]- height[j]), where abs() means the absolute difference.
- We need to return the minimum energy that can be used by the frog to jump from stair 0 to stair N-1.
Memoization Approach (Top Down):
def frogJump(n: int, heights: List[int]) -> int:
dp = [0] + [-1] * (n - 1)
def dfs(idx):
if idx == 0:
return 0
if idx == 1:
dp[idx] = dfs(idx-1) + abs(heights[idx] - heights[idx - 1])
return dp[idx]
if dp[idx] != -1:
return dp[idx]
left = dfs(idx-1) + abs(heights[idx] - heights[idx - 1])
right = dfs(idx-2) + abs(heights[idx] - heights[idx - 2])
dp[idx] = min(left, right)
return dp[idx]
dfs(n-1)
return dp[n-1]
Tabular Approach (Bottom Up):
def frogJump(n: int, heights: List[int]) -> int:
dp = [-1] * (n)
dp[0] = 0
dp[1] = abs(heights[1] - heights[0])
for i in range(2, n):
dp[i] = min(
dp[i-1] + abs(heights[i-1] - heights[i]),
dp[i-2] + abs(heights[i-2] - heights[i])
)
return dp[-1]
Tabular Approach Space Optimized (Bottom Up):
def frogJump(n: int, heights: List[int]) -> int:
dp = [-1] * (n)
dp_0 = 0
dp_1 = abs(heights[1] - heights[0])
for i in range(2, n):
dp_i = min(
dp_0 + abs(heights[i-1] - heights[i]),
dp_1 + abs(heights[i-2] - heights[i])
)
dp_0 = dp_1
dp_1 = dp_i
return dp_1
Follow up problem: https://atcoder.jp/contests/dp/tasks/dp_b If instead of 2 jumps i.e i+1 and i+2, there are k jumps i+1, i+2, ..., i+k. How to solve this?
Tabular Solution:
def frogJump(n: int, k: int, heights: List[int]) -> int:
dp = [-1] * n
dp[0] = 0
for i in range(1, n):
min_val = float("inf")
for j in range(i-1, max(i-k-1, -1), -1):
curr_val = dp[j] + abs(stones[i] - stones[j])
if curr_val < min_val:
min_val = curr_val
dp[i] = min_val
return dp[n-1]
Maximum sum of non-adjacent elements | House Robber
Problem Statement:
Memoization Approach (Top Down):
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [-1] * n
def dfs(idx):
if idx == 0:
dp[idx] = nums[idx]
return nums[idx]
if idx < 0:
return 0
if dp[idx] != -1:
return dp[idx]
left = dfs(idx-2) + nums[idx]
right = dfs(idx-1)
dp[idx] = max(left, right)
return dp[idx]
dfs(n-1)
return dp[n-1]
Tabular Approach (Bottom Up):
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
pick = nums[i]
if i > 1:
pick += dp[i-2]
not_pick = dp[i-1]
dp[i] = max(pick, not_pick)
return dp[n-1]
Tabular Approach Space Optimized (Bottom Up):
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
adj_house = nums[0]
non_adj = 0
for i in range(1, n):
pick = nums[i] + non_adj
not_pick = adj_house
curr_pick = max(pick, not_pick)
non_adj = adj_house
adj_house = curr_pick
return adj_house
House Robber Part-2
Problem Statement:
- You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
- Given an integer array
numsrepresenting the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Solution Approach:
- We can use the same code from the House Robber part 1 and just run the code for including the first and removing last element or else adding last and removing first element and take the maximum value from both of them.
Memoization Approach (Top Down):
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [-1] * n
def dfs(idx, low):
if idx == low:
dp[idx] = nums[idx]
return dp[idx]
if idx < low:
return 0
if dp[idx] != -1:
return dp[idx]
left = dfs(idx-2, low) + nums[idx]
right = dfs(idx-1, low)
dp[idx] = max(left, right)
return dp[idx]
dp_n = dfs(n-1, 1)
dp = [-1] * n
dp_n_1 = dfs(n-2, 0)
return max(dp_n, dp_n_1)
Tabular Approach Space Optimized (Bottom Up):
class Solution:
def dfs(self, houses):
adj_house = houses[0]
non_adj = 0
for i in range(1, len(houses)):
curr_pick = max(non_adj + houses[i], adj_house)
non_adj = adj_house
adj_house = curr_pick
return adj_house
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return nums[0]
return max(self.dfs(nums[:-1]), self.dfs(nums[1:]))
2D Dynamic Programming
Problems:
Ninja Training:
Problem Statement:
- Ninja is planing this ‘N’ days-long training schedule.
- Each day, he can perform any one of these three activities. (Running, Fighting Practice or Learning New Moves).
- Each activity has some merit points on each day. As Ninja has to improve all his skills, he can’t do the same activity in two consecutive days. Can you help Ninja find out the maximum merit points Ninja can earn?
- You are given a 2D array of size
N * 3‘POINTS’ with the points corresponding to each day and activity. Your task is to calculate the maximum number of merit points that Ninja can earn.
Memoization Approach (Top Down): Time : O((N * 4) * 3)) Space: O(N) + O(N * 4)
from typing import *
def dfs(day, last, points, dp):
if day == 0:
maxi = 0
for i in range(3):
if i != last:
maxi = max(maxi, points[0][i])
return maxi
if dp[day][last] != -1:
return dp[day][last]
maxi = 0
for i in range(3):
if i != last:
point = points[day][i] + dfs(day-1, i, points, dp)
maxi = max(maxi, point)
dp[day][last] = maxi
return maxi
def ninjaTraining(n: int, points: List[List[int]]) -> int:
dp = [[-1] * 4 for _ in range(n)]
return dfs(n - 1, 3, points, dp)
Tabular Approach (Bottom Up): Time : O((N * 4) * 3)) Space: O(N * 4)
def ninjaTraining(n: int, points: List[List[int]]) -> int:
dp = [[-1] * 4 for _ in range(n)]
dp[0][0] = max(points[0][1], points[0][2])
dp[0][1] = max(points[0][0], points[0][2])
dp[0][2] = max(points[0][0], points[0][1])
dp[0][3] = max(points[0][0], max(points[0][1], points[0][2]))
for i in range(1, n):
for last in range(4):
maxi = 0
for current in range(3):
if current != last:
point = points[i][current] + dp[i-1][current]
maxi = max(point, maxi)
dp[i][last] = maxi
return dp[n-1][3]
Tabular Approach Space Optimized (Bottom Up): Time : O((N * 3) * 3)) Space: O(1)
def ninjaTraining(n: int, points: List[List[int]]) -> int:
dp = [-1] * 3
dp[0] = max(points[0][1], points[0][2])
dp[1] = max(points[0][0], points[0][2])
dp[2] = max(points[0][0], points[0][1])
# dp[3] = max(points[0][0], max(points[0][1], points[0][2]))
for i in range(1, n):
temp = [0] * 3
for last in range(3):
for current in range(3):
if current != last:
point = points[i][current] + dp[current]
temp[last] = max(point, temp[last])
dp = temp
return max(dp[0], max(dp[1], dp[2]))
DP on Grid problems:
Unique Paths:
Problem Statement:
- There is a robot on an
m x ngrid. The robot is initially located at the top-left corner (i.e.,grid[0][0]). The robot tries to move to the bottom-right corner (i.e.,grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. - Given the two integers
mandn, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
Memoization Approach (Top Down): Time : O(N * M) Space: O(N * M) + O(N * M)
class Solution:
def dfs(self, i, j, dp):
if (i, j) == (0, 0):
return 1
if dp[i][j] != -1:
return dp[i][j]
ans = 0
if i-1 >= 0:
ans += self.dfs(i-1, j, dp)
if j -1 >= 0:
ans += self.dfs(i, j - 1, dp)
dp[i][j] = ans
return ans
def uniquePaths(self, m: int, n: int) -> int:
dp = [[-1] * n for _ in range(m)]
return self.dfs(m-1, n-1, dp)
Tabular Approach (Bottom Up): Time : O(N * M) Space: O(N * M)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[-1] * n for _ in range(m)]
dp[0][0] = 1
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
up = 0
if i > 0:
up = dp[i-1][j]
left = 0
if j > 0:
left = dp[i][j-1]
dp[i][j] = up + left
return dp[m-1][n-1]
Tabular Approach Space Optimized (Bottom Up): Time : O(N * M) Space: O(1)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
prev = [0] * n
for i in range(m):
temp = [0] * n
for j in range(n):
if i == 0 and j == 0:
temp[j] = 1
continue
up = 0
if i > 0:
up = prev[j]
left = 0
if j > 0:
left = temp[j-1]
temp[j] = up + left
prev = temp
return prev[n-1]
Unique Paths 2:
Problem Statement:
- You are given an
m x ninteger arraygrid. There is a robot initially located at the top-left corner (i.e.,grid[0][0]). The robot tries to move to the bottom-right corner (i.e.,grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. - An obstacle and space are marked as
1or0respectively ingrid. A path that the robot takes cannot include any square that is an obstacle. - Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
Memoization Approach (Top Down): Time : O(N * M) Space: O(N * M) + O(N * M)
class Solution:
def dfs(self, i, j, dp, grid):
if grid[i][j] == 1:
return 0
if (i, j) == (0, 0):
return 1
if dp[i][j] != -1:
return dp[i][j]
ans = 0
if i-1 >= 0:
ans += self.dfs(i-1, j, dp, grid)
if j -1 >= 0:
ans += self.dfs(i, j - 1, dp, grid)
dp[i][j] = ans
return ans
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[-1] * n for _ in range(m)]
return self.dfs(m-1, n-1, dp, obstacleGrid)
Tabular Approach (Bottom Up): Time : O(N * M) Space: O(N * M)
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[-1] * n for _ in range(m)]
dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
continue
up = 0
if i > 0:
up = dp[i-1][j]
left = 0
if j > 0:
left = dp[i][j-1]
dp[i][j] = up + left
return dp[m-1][n-1]
Tabular Approach Space Optimized (Bottom Up): Time : O(N * M) Space: O(1)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
prev = [0] * n
for i in range(m):
temp = [0] * n
for j in range(n):
if i == 0 and j == 0:
temp[j] = 1
continue
up = 0
if i > 0:
up = prev[j]
left = 0
if j > 0:
left = temp[j-1]
temp[j] = up + left
prev = temp
return prev[n-1]