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.
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:
- Some DP problems can only use O(1) space
LintCode: Computer Maintenance - We don’t always need the base case
Bomb Enemy - 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
- Instead of left-to-right, do it from right-to-left: Maximum Length of Repeated Subarray
The most impressive problems to me:
See all dynamicprogramming problems: #dynamicprogramming
- Review: Dynamic Programming Problems
- LintCode: Minimum Cycle Section
- LintCode: Frog Jump
- Lintcode: Digital Flip
- LintCode: Computer Maintenance
- LintCode: Card Game
- Leetcode: Word Break
- Leetcode: Unique Paths II
- Leetcode: Unique Paths
- Leetcode: Unique Binary Search Trees II
- Leetcode: Unique Binary Search Trees
- Leetcode: Triangle
- Leetcode: Student Attendance Record II
- Leetcode: Remove Boxes
- Leetcode: Race Car
- Leetcode: Partition Equal Subset Sum
- Leetcode: Paint House
- Leetcode: Paint Fence
- Leetcode: Ones and Zeroes
- Leetcode: New 21 Game
- Leetcode: Minimum Swaps To Make Sequences Increasing
- Leetcode: Minimum Path Sum
- Leetcode: Minimum Falling Path Sum
- Leetcode: Min Cost Climbing Stairs
- Leetcode: Maximum Length of Repeated Subarray
- Leetcode: Maximum Length of Pair Chain
- Leetcode: Maximal Square
- Leetcode: Longest Palindromic Subsequence
- Protected: Leetcode: Longest Line of Consecutive One in Matrix
- Leetcode: Longest Increasing Subsequence
- Leetcode: Length of Longest Fibonacci Subsequence
- Leetcode: Largest Sum of Averages
- Leetcode: Largest Divisible Subset
- Leetcode: Interleaving String
- Leetcode: Integer Break
- Leetcode: House Robber II
- Leetcode: House Robber
- Leetcode: Gray Code
- Leetcode: Flip String to Monotone Increasing
- Leetcode: Find the Derangement of An Array
- Leetcode: Fibonacci Number
- Leetcode: Edit Distance
- Leetcode: Dungeon Game
- Leetcode: Domino and Tromino Tiling
- Leetcode: Divisor Game
- Leetcode: Delete Operation for Two Strings
- Leetcode: Counting Bits
- Leetcode: Count Primes
- Leetcode: Combination Sum IV
- Leetcode: Climbing Stairs
- Leetcode: Champagne Tower
- Leetcode: Can I Win
- Leetcode: Bomb Enemy
- Leetcode: Bitwise ORs of Subarrays
- Leetcode: Arithmetic Slices II – Subsequence
- Leetcode: All Possible Full Binary Trees
- Leetcode: 2 Keys Keyboard
See more blog_posts.
Share It, If You Like It.