Review: Dynamic Programming Problems

Posted on January 22, 2018November 17, 2019 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
Optimal Substructure
DP vs recursive+memoization
Non-linear dynamic problem problems	Leetcode: Minimum Score Triangulation of Polygon

Questions

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
2-D dp, instead of one	Leetcode: Longest Common Subsequence, Leetcode: Edit Distance
DP breaks down into two subproblems, instead of one	Leetcode: Minimum Score Triangulation of Polygon
Instead of based on possible actions, based on states	Leetcode: Best Time to Buy and Sell Stock with Cooldown

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:

CheatSheet: Leetcode For Code Interview

See all dynamicprogramming problems: #dynamicprogramming

See more blog_posts.

Post Views: 10