Day 21 of 30 days of Data Structures and Algorithms and System Design Simplified — 2-D Dynamic Programming
Welcome back peeps. Hope all’s well. In this post we will cover Dynamic Programming technique ( 2D Dynamic Programming) as follows —
What and Why 2D Dynamic Programming technique(in 2–3 sentences)?
How does 2 D Dynamic Programming technique work?
Important Patterns and Techniques in Dynamic Programming technique Questions
Most Important Questions with Solutions
Tips and Techniques to solve Dynamic Programming technique Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Dynamic Programming
Importance : Very High
Note : New Dynamic Programming questions with solutions will be added everyday. So keep checking this post daily.
Let’s dive in!
What is Dynamic Programming?
Dynamic programming is a technique for solving problems which are defined by recurrences with overlapping sub problems.
This technique solves the class of problems that have overlapping subproblems and optimal substructure property.
The problems are solved in bottom up manner and the optimal solution is constructed using the computed values/solution of the sub problems.
Examples of dynamic programming problems —
Longest Common Subsequence Problem.
Shortest Common Super sequence Problem.
Longest Increasing Subsequence Problem.
Matrix Chain Multiplication Problem.
0–1 Knapsack Problem.
Partition Problem etc
There are two types of DP problems —
- 1D DP problems
The types of problems in which during recursion only one parameter changes its values.
- 2D DP problems
The types of problems in which during recursion two parameter change their values.
In this post we will see 1D Dynamic programming problems in detail.
How does 2D Dynamic Programming work?
2D Dynamic programming is a technique for solving problems by breaking them down into smaller subproblems and storing the solutions to those subproblems in a 2-dimensional table or array to avoid redundant work. This technique is often used to solve problems that have overlapping subproblems, which can be identified by a recursive structure and have a 2-dimensional input or output.
2D Dynamic programming technique typically involves breaking the problem down into smaller subproblems, solving each subproblem, and storing the result in a 2-dimensional table or array. The solutions to the subproblems are then used to solve the larger problem, by combining or modifying the stored solutions in some way.
The main gist is — solve all the sub problems, make decisions at every stage and then select one that helps to find the most optimal solution.
In this sub problems are dependent which means the sub problems share sub-sub problems and every sub-sub problem is solved just once and the solutions to sub-sub problems are stored in a table and later used to solve the higher level sub problems.
2D Dynamic programming problems are solved using 2D array or matrix.
Important Patterns and Techniques in 2D Dynamic Programming Questions
Important patterns and techniques in 2D dynamic programming questions include identifying the overlapping subproblems, understanding how the subproblems relate to the original problem, and recognizing the appropriate time to use 2D dynamic programming.
Dynamic Programming problems can be divided into two types: optimization problems and combinatoric problems.
To solve Dynamic programming problem —
1.Divide the problem into subproblem and find a recursive ( best is recursive DFS) relation.
2. Find the optimal solutions of the sub‐ problems and approach bottom up.
3. Use memoization to eliminate redundancy i.e save the intermediate results and cache them.
Patterns → Questions like below belong to Dynamic Programming technique( not limited to):
Find a path
Find max path
Find min path
Longest Path in a matrix etc
For the 2D Dynamic problems, you should know how to traverse the matrix using left, right, top and down pointers.
Most Important Questions with Solutions
Note : New Dynamic Programming questions with solutions are added every day. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Dynamic Programming questions.
Unique Paths
Question —
There is a robot on an m x n grid. 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 m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
Example :
Input: m = 3, n = 7
Output: 28Solution :
Main Logic/Idea —
The main logic is to do bottom up approach. Start from the last cell and build a new row and column with default value as 1 ( since the steps to reach destination from the new cell is 1). Once done, calculate the steps to reach the target using by adding column j+1 and row at j pointer.
Implementation —
def uniquePaths(self, m: int, n: int) -> int:
row = [1] * n
for i in range(m-1):
newR = [1]*n
for j in range(n-2,-1,-1):
newR[j] = newR[j+1] + row[j]
row = newR
return row[0]Question Link
Similar Pattern —
Minimum Cost Homecoming of a Robot in a Grid
Number of Ways to Reach a Position After Exactly k Steps
Paths in Matrix Whose Sum Is Divisible by K
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Longest Increasing Path in a Matrix
Question —
Given an m x n integers matrix, return the length of the longest increasing path in matrix.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
Example :
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4Solution :
Main Logic/Idea —
The main logic is to go through the matrix by performing recursive dfs ( in all the directions) and return the longest increasing path. Check for the boundary conditions at every step.
Implementation —
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
rows, cols, temp = len(matrix), len(matrix[0]),{}
def calcPath(r,c,previousVal):
ans = 1
if (r<0 or r == rows or c<0 or c==cols or matrix[r][c] <= previousVal):
return 0
if (r,c) in temp:
return temp[(r,c)]
ans = max(ans,1+calcPath(r+1,c,matrix[r][c]))
ans = max(ans,1+calcPath(r,c+1,matrix[r][c]))
ans = max(ans,1+calcPath(r-1,c,matrix[r][c]))
ans = max(ans,1+calcPath(r,c-1,matrix[r][c]))
temp[(r,c)] = ans
return ans
for ro in range(rows):
for co in range(cols):
calcPath(ro,co,-1)
return max(temp.values())Question Link
Similar Pattern —
Number of Increasing Paths in a Grid
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Minimum Path Sum
Question —
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
You can only move either down or right at any point in time.
Example :
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7Solution :
Main Logic/Idea —
The main logic is to calculate the min path top down ( go left, right, top and bottom) fo reach column and row and lastly return the min.
Implementation —
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m=len(grid)
n=len(grid[0])
for i in range(1, n):
grid[0][i]+=grid[0][i-1]
for j in range(1,m):
grid[j][0]+=grid[j-1][0]
for i in range(1,m):
for j in range(1,n):
grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
return grid[-1][-1]Question Link
Similar Pattern —
Maximum Number of Points with Cost
Minimum Cost Homecoming of a Robot in a Grid
Paths in Matrix Whose Sum Is Divisible by K
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Dynamic Programming questions with solutions will be added everyday. So keep checking this post daily.
Tips and Techniques to solve 2-D Dynamic Programming Questions Fast —
Remember the gist of dynamic problem is to find the solution to the sub sequence/sub problems.
Most of the Dynamic Programming problems appear with optimal substructures where by optimally solving a sequence of local problems, one can reach to a globally optimal solution.
To solve the dynamic programming questions fast —
- Know how to calculate bottom — up and top — down result.
- Know how to initialize the 2D array with new row and column.
- Know how to solve sub problems and combine together the sub results.
That’s it for now. Day 22: Intervals technique coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
