Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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(n2) LeetCode: Longest Palindromic Substring
6 Edit distance of two strings O(n2) LeetCode: Edit Distance
7 Maximal Square O(n*m) Leetcode: Maximal Square
8 Maximum profits with certain costs O(n2) 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(n*m*N) 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(n3) LeetCode: Minimum Cost to Merge Stones
17 DP over interval: Minimum-weight triangulation O(n3) LeetCode: Minimum Score Triangulation of Polygon
18 Burst Balloons O(n3) 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(n4) LeetCode: Remove Boxes
21 Largest Sum of Averages O(k*n*n) LeetCode: Largest Sum of Averages
22 Uncrossed Lines O(n*m) LeetCode: Uncrossed Lines
23 treedp: Binary Trees With Factors O(n2) 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:

  1. Key observation is crucial. Watch careful for how the states transit?
  2. 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:

  • Min Cost Climbing Stairs
  • Maximum Length of Repeated Subarray

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups

See all dynamicprogramming problems: #dynamicprogramming

  • Review: Dynamic Programming Problems
  • LintCode: Minimum Cycle Section
  • Lintcode: Digital Flip
  • LintCode: Computer Maintenance
  • LeetCode: Zuma Game
  • LeetCode: Word Break
  • LeetCode: Wildcard Matching
  • LeetCode: Video Stitching
  • LeetCode: Valid Palindrome III
  • LeetCode: Unique Substrings in Wraparound String
  • LeetCode: Unique Paths II
  • LeetCode: Unique Paths
  • LeetCode: Unique Binary Search Trees II
  • LeetCode: Unique Binary Search Trees
  • LeetCode: Uncrossed Lines
  • LeetCode: Ugly Number II
  • LeetCode: Triangle
  • LeetCode: Toss Strange Coins
  • LeetCode: Text Justification
  • LeetCode: Target Sum
  • LeetCode: Tallest Billboard
  • LeetCode: Student Attendance Record II
  • LeetCode: Strange Printer
  • LeetCode: Stone Game II
  • LeetCode: Stone Game
  • LeetCode: Split Array Largest Sum
  • LeetCode: Smallest Sufficient Team
  • LeetCode: Shortest Path with Alternating Colors
  • LeetCode: Shortest Common Supersequence
  • LeetCode: Shopping Offers
  • LeetCode: Restore The Array
  • LeetCode: Remove Boxes
  • LeetCode: Regular Expression Matching
  • LeetCode: Race Car
  • LeetCode: Partition to K Equal Sum Subsets
  • LeetCode: Partition Equal Subset Sum
  • LeetCode: Palindrome Removal
  • LeetCode: Palindrome Partitioning III
  • LeetCode: Palindrome Partitioning II
  • LeetCode: Paint House III
  • LeetCode: Paint House
  • LeetCode: Paint Fence
  • LeetCode: Out of Boundary Paths
  • LeetCode: Ones and Zeroes
  • LeetCode: One Edit Distance
  • LeetCode: Numbers With Same Consecutive Differences
  • LeetCode: Number of Ways to Wear Different Hats to Each Other
  • LeetCode: Number of Ways to Stay in the Same Place After Some Steps
  • LeetCode: Number of Ways to Paint N x 3 Grid
  • LeetCode: Number of Ways of Cutting a Pizza
  • LeetCode: New 21 Game
  • LeetCode: Minimum Swaps To Make Sequences Increasing
  • LeetCode: Minimum Score Triangulation of Polygon
  • LeetCode: Minimum Path Sum
  • LeetCode: Minimum Number of Taps to Open to Water a Garden
  • LeetCode: Minimum Falling Path Sum II
  • LeetCode: Minimum Falling Path Sum
  • LeetCode: Minimum Distance to Type a Word Using Two Fingers
  • LeetCode: Minimum Difficulty of a Job Schedule
  • LeetCode: Minimum Cost Tree From Leaf Values
  • LeetCode: Minimum Cost to Merge Stones
  • LeetCode: Minimum Cost For Tickets
  • LeetCode: Minimum ASCII Delete Sum for Two Strings
  • LeetCode: Min Cost Climbing Stairs
  • LeetCode: Maximum Vacation Days
  • LeetCode: Maximum Students Taking Exam
  • LeetCode: Maximum Profit in Job Scheduling
  • LeetCode: Maximum Length of Repeated Subarray
  • LeetCode: Maximum Length of Pair Chain
  • LeetCode: Maximal Square
  • LeetCode: Make Array Strictly Increasing
  • LeetCode: Longest Turbulent Subarray
  • LeetCode: Longest String Chain
  • LeetCode: Longest Palindromic Subsequence
  • Protected: LeetCode: Longest Line of Consecutive One in Matrix
  • LeetCode: Longest Increasing Subsequence
  • LeetCode: Longest Common Subsequence
  • LeetCode: Longest Arithmetic Subsequence of Given Difference
  • LeetCode: Length of Longest Fibonacci Subsequence
  • LeetCode: Last Stone Weight II
  • LeetCode: Largest Sum of Averages
  • LeetCode: Largest Divisible Subset
  • LeetCode: Knight Dialer
  • LeetCode: Jump Game V
  • LeetCode: Interleaving String
  • LeetCode: Integer Break
  • LeetCode: House Robber II
  • LeetCode: House Robber
  • LeetCode: Grumpy Bookstore Owner
  • LeetCode: Gray Code
  • LeetCode: Frog Jump
  • LeetCode: Flip String to Monotone Increasing
  • LeetCode: Find the Derangement of An Array
  • LeetCode: Find All Good Strings
  • LeetCode: Filling Bookcase Shelves
  • LeetCode: Fibonacci Number
  • LeetCode: Edit Distance
  • LeetCode: Dungeon Game
  • LeetCode: Domino and Tromino Tiling
  • LeetCode: Divisor Game
  • LeetCode: Distinct Subsequences II
  • LeetCode: Delete Operation for Two Strings
  • LeetCode: Counting Bits
  • LeetCode: Count Vowels Permutation
  • LeetCode: Count Triplets That Can Form Two Arrays of Equal XOR
  • LeetCode: Count Square Submatrices with All Ones
  • LeetCode: Count Primes
  • LeetCode: Count Number of Teams
  • LeetCode: Count All Valid Pickup and Delivery Options
  • LeetCode: Constrained Subset Sum
  • LeetCode: Constrained Subsequence Sum
  • LeetCode: Combination Sum IV
  • LeetCode: Coin Path
  • LeetCode: Climbing Stairs
  • LeetCode: Champagne Tower
  • LeetCode: Can I Win
  • LeetCode: Burst Balloons
  • LeetCode: Build Array Where You Can Find The Maximum Exactly K Comparisons
  • LeetCode: Bomb Enemy
  • LeetCode: Bitwise ORs of Subarrays
  • LeetCode: Binary Trees With Factors
  • LeetCode: Binary Tree Cameras
  • LeetCode: Best Time to Buy and Sell Stock with Transaction Fee
  • LeetCode: Best Time to Buy and Sell Stock with Cooldown
  • LeetCode: Arithmetic Slices II – Subsequence
  • LeetCode: All Possible Full Binary Trees
  • LeetCode: Airplane Seat Assignment Probability
  • LeetCode: 4 Keys Keyboard
  • LeetCode: 2 Keys Keyboard

See more blog posts.

linkedin
github
slack

Post Views: 10
Posted in ReviewTagged #dynamicprogramming, review

Post navigation

Review: Graph Problems
Review: Greedy Problems

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.