Dynamic Programming
Dynamic Programming
What is Dynamic Programming (DP)?
Dynamic Programming (DP) is a method used in mathematics and computer science to solve complex problems by breaking them down into simpler subproblems. By solving each subproblem only once and storing the results, it avoids redundant computations, leading to more efficient solutions for a wide range of problems.
How Does Dynamic Programming (DP) Work?
- Identify Subproblems: Divide the main problem into smaller, independent subproblems.
- Store Solutions: Solve each subproblem and store the solution in a table or array.
- Build Up Solutions: Use the stored solutions to build up the solution to the main problem.
- Avoid Redundancy: By storing solutions, DP ensures that each subproblem is solved only once, reducing computation time.
When to Use Dynamic Programming (DP)?
Dynamic programming is an optimization technique used when solving problems that consists of the following characteristics:
- Optimal Substructure: Optimal substructure means that we combine the optimal results of subproblems to achieve the optimal result of the bigger problem.
- Overlapping Subproblems: The same subproblems are solved repeatedly in different parts of the problem.
Exercise
Fundamental Problems
509: Fibonacci Number
70: Climbing Stairs
1137: N-th Tribonacci Number
746: Min Cost Climbing Stairs
740: Delete and Earn
198: House Robber
343: Integer Break
Matrix
62: Unique Paths
64: Minimum Path Sum
63: Unique Paths II
120: Triangle
931: Minimum Falling Path Sum
221: Maximal Square
Knapsack Problem
416: Partition Equal Subset Sum
1049: Last Stone Weight II
494: Target Sum
474: Ones and Zeroes
Knapsack Problem
518: Coin Change II
322: Coin Change
279: Perfect Squares
377: Combination Sum IV
139: Word Break
House Robber
213: House Robber II
337: House Robber III
96: Unique Binary Search Trees
95: Unique Binary Search Trees II
124: Binary Tree Maximum Path Sum
Buy and Sell Stock
121: Best Time to Buy and Sell Stock
123: Best Time to Buy and Sell Stock III
188: Best Time to Buy and Sell Stock IV
309: Best Time to Buy and Sell Stock with Cooldown
Subsequence
1143: Longest Common Subsequence
1035: Uncrossed Lines
300: Longest Increasing Subsequence
673: Number of Longest Increasing Subsequence
1312: Minimum Insertion Steps to Make a String Palindrome
646: Maximum Length of Pair Chain
1218: Longest Arithmetic Subsequence of Given Difference
1027: Longest Arithmetic Subsequence
354: Russian Doll Envelopes
1964: Find the Longest Valid Obstacle Course at Each Position
Subsequence
674: Longest Continuous Increasing Subsequence
718: Maximum Length of Repeated Subarray
Edit Distance
392: Is Subsequence
115: Distinct Subsequences
583: Delete Operation for Two Strings
712: Minimum ASCII Delete Sum for Two Strings
72: Edit Distance
Palindrome
5: Longest Palindromic Substring
647: Palindromic Substrings
516: Longest Palindromic Subsequence
Other
2140: Solving Questions With Brainpower
2466: Count Ways To Build Good Strings
91: Decode Ways
983: Minimum Cost For Tickets
790: Domino and Tromino Tiling