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 |
Scenarios Code Skeleton Questions
| Name | Example |
|---|
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 [display-posts tag=”dynamicprogramming” posts_per_page=”100” orderby=”title”]
See more blog_posts.
动态规划 动态规划（dynamic programming）多应用于子问题重叠的情况,每个子问题只求解一次.动态规划方法通常用来求解最优化问题的一个最优解. 设计动态规划方法的4个步骤: 刻画一个最优解的结构特征 递归地定义最优解的值 计算最优解的值,通常采用自底向上的方法 利用计算出的信息构造一个最优解 最优子结构（optimal substructure） 问题的最优解由相关子问题的最优解组合而成,而这些子问题可以独立求解.