Day 7 of 30 days of Data Structures and Algorithms and System Design Simplified — 1 D Dynamic Programming
Welcome back peeps. Hope all’s well. In this post we will cover Dynamic Programming technique ( 1D) as follows —
What and Why Dynamic Programming technique(in 2–3 sentences)?
How does 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 everyday.
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 Dynamic Programming work?
Dynamic Programming is a technique for solving problems by breaking them down into smaller subproblems and storing the solutions to those subproblems to avoid redundant work. This technique is often used to solve problems that have overlapping subproblems, which can be identified by a recursive structure.
The dynamic programming technique typically involves breaking the problem down into smaller subproblems, solving each subproblem and storing the result in a table or an 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.
Important Patterns and Techniques in Dynamic Programming Questions
Important patterns and techniques in dynamic programming questions include identifying the overlapping subproblems, understanding how the subproblems relate to the original problem, and recognizing the appropriate time to use 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):
Min/Max Cost
Path Sum
Coin Change
1 D Path/houses to rob
Paint houses/fences
Flower the garden ( max flowers that you can plant)
Longest Palindromic substring etc
Most Important Questions with Solutions
Note : New Dynamic Programming questions with solutions are added every day. So keep checking this post day.
Golden rule is — Learn by doing/implementing
In this we will see most important Dynamic Programming questions.
House Robber II
Question —
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 nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example :
Input: nums = [2,3,2]
Output: 3Solution :
Main Logic/Idea —
The main logic is to use array slicing to make sure robing first house doesn’t overlap with the last house. You can either rob the first house + n houses or start robbing from the second house and keep updating the house rob variable.
Implementation —
def rob(self, nums: List[int]) -> int:
return max(nums[0],self.robhelper(nums[1:]),self.robhelper(nums[:-1]))
def robhelper(self,nums):
rob1,rob2 = 0,0
for n in nums:
ans = max( rob1+n, rob2)
rob1 = rob2
rob2 = ans
return rob2Question Link
Similar Pattern —
Non-negative Integers without Consecutive Ones
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Coin Change
Question —
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Example :
Input: coins = [1,2,5], amount = 11
Output: 3Solution :
Main Logic/Idea —
The main logic is to see how to make the total amount with one coin and then minus that coin from the total amount to make that amount with other coins. For example dp[7] = 1+dp[7–3] assuming the coin denomination is 3.
Implementation —
def coinChange(self, coins: List[int], amount: int) -> int:
ans = [amount +1 ] * (amount +1)
ans[0] = 0
for amt in range( 1, amount+1):
for cn in coins :
if amt - cn >= 0:
ans[amt] = min(ans[amt], 1+ans[amt-cn])
return ans[amount] if ans[amount] != amount +1 else -1Question Link
Similar Pattern —
Maximum Value of K Coins From Piles
Minimum Number of Operations to Convert Time
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Binary Tree Maximum Path Sum
Question —
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Example :
Input: root = [1,2,3]
Output: 6Solution :
Main Logic/Idea —
The main logic is to calculate the path with or without splitting. Calculate the left path and the right path and add it to the node value. Then find the max of path obtained with or without splitting.
Implementation —
def maxPathSum(self, root: Optional[TreeNode]) -> int:
ans = [root.val]
def calpath(node):
if not node: return 0
lMax = calpath(node.left)
rMax = calpath(node.right)
lMax = max(lMax,0)
rMax = max(rMax,0)
ans[0] = max(ans[0], node.val + lMax + rMax)
return node.val + max(lMax,rMax)
calpath(root)
return ans[0]Question Link
Similar Pattern —
Time Needed to Inform All Employees
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Dynamic Programming questions with solutions are added every day. So keep checking this post day.
Tips and Techniques to solve 1-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 —
First create a solution with decision tree.
See which part of the decision tree in repeating for the sub problems.
Cache/Memoize the part that’s repeating and then find the optimal solution to the subproblem
Once optimal solutions to all the subproblems are calculated then combine them to develop the globally optimal solution.
That’s it for now. Day 8 : Two pointer 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
