Review: Dynamic Programming Problems

Posted on January 22, 2018July 26, 2020 by braindenny

Dynamic programming problems scare me A LOT.

Yeah, it could be quite frustrating, if you haven’t found the key assertions.

Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.

The main idea behind DP is to save duplicated caculations.

Trade space for time.

Basic Abstractions

Name	Summary
Typical dynamicprogramming problems	#knapsack, #intervaldp, #treedp, #bitmaskdp
Typical dynamicprogramming problems	#divideconquer, #lis, #lcs, #minimax, #coin
Typical dynamicprogramming problems	#paintfence, #frogjump, #houserobber
Optimal Substructure
DP vs recursive+memoization

Top Questions

Num	Problem	Time Complexity	Summary
1	Maximum subarray problem – Kadane’s algorithm	O(n)	LeetCode: Maximum Subarray
2	LIS – Longest increasing subsequence	O(n)	LeetCode: Longest Increasing Subsequence
3	LCS – Longest Common Subsequence	O(n*m)	LeetCode: Longest Common Subsequence
4	LPS – Longest Palindromic Subsequence	O(n)	LeetCode: Longest Palindromic Subsequence
5	Longest Palindromic Substring	O(n²)	LeetCode: Longest Palindromic Substring
6	Edit distance of two strings	O(n²)	LeetCode: Edit Distance
7	Maximal Square	O(n*m)	Leetcode: Maximal Square
8	Maximum profits with certain costs	O(n²)	LeetCode: 4 Keys Keyboard
9	Count of distinct subsequence	O(n)	LeetCode: Distinct Subsequences II
10	Count out of boundary paths in a 2D matrix	O(nmN)	LeetCode: Out of Boundary Paths
11	Regular Expression Matching	O(n*m)	LeetCode: Regular Expression Matching
12	Wildcard Matching	O(n*m)	LeetCode: Wildcard Matching
13	Multiple choices for each step	O(n*m)	LeetCode: Filling Bookcase Shelves
14	Knapsack: put array to bag A, B or discard it	O(n*s)	LeetCode: Tallest Billboard
15	Knapsack problem to maximize benefits	O(n*s)	LeetCode: Coin Change
16	Minimum Cost to Merge Stones	O(n³)	LeetCode: Minimum Cost to Merge Stones
17	DP over interval: Minimum-weight triangulation	O(n³)	LeetCode: Minimum Score Triangulation of Polygon
18	Burst Balloons	O(n³)	LeetCode: Burst Balloons
19	DP based on states, instead of possible actions	O(n)	LeetCode: Best Time to Buy and Sell Stock with Cooldown
20	Remove Boxes	O(n⁴)	LeetCode: Remove Boxes
21	Largest Sum of Averages	O(knn)	LeetCode: Largest Sum of Averages
22	Uncrossed Lines	O(n*m)	LeetCode: Uncrossed Lines
23	treedp: Binary Trees With Factors	O(n²)	LeetCode: Binary Trees With Factors
24	DP based on values instead of positions	O(n)	LeetCode: Minimum Distance to Type a Word Using Two Fingers
25	Video Stitching	O(n*m)	LeetCode: Video Stitching
26	Maximum Profit in Job Scheduling	O(n*log(n))	Leetcode: Maximum Profit in Job Scheduling
27	Machine state	O(n)	Leetcode: Student Attendance Record II
28	dp + greedy	O(n)	Leetcode: House Robber

Name	Example
DP needs only O(1) space	LintCode: Computer Maintenance
Some initialization can be skipped	LeetCode: Longest Arithmetic Subsequence of Given Difference
Some initialization can be skipped	LeetCode: Bomb Enemy
Instead of left-to-right, do it from right-to-left	Maximum Length of Repeated Subarray, LeetCode: Largest Sum of Averages
Ugly Number II	LeetCode: Ugly Number II
DP based on values instead of positions	LeetCode: Minimum Distance to Type a Word Using Two Fingers

Key Parts In DP Problems:

Key observation is crucial. Watch careful for how the states transit?
Walk through with smaller cases manually. And detect the pattern.

Different Types Of DP Functions:

Interesting dp funcitons
Domino and Tromino Tiling
dp(i) = dp(i-1)+dp(i-2)+2*(dp(i-3)+dp(i-4)+…+dp(0))
DP saves intermediate results, not the final ones
Champagne Tower
dp(i) = min(dp(i), dp[i-coin[j]]+1)
Coin Change
Function: f(i, j): Longest Palindromic Subsequence
Coin Change 2
Save the base case: Maximum Length of Repeated Subarray

The most impressive problems to me:

See all dynamicprogramming problems: #dynamicprogramming

See more blog posts.

Post Views: 10