Dynamic programming
Last updated
Was this helpful?
Last updated
Was this helpful?
f[i] 第i个
f[i] 前i个
can be O(1) variable or O(n)/1D variable
these problems are conditional, discuss different situation:
Stocks: the whole series key point: buy and sell must cannot happen together, because if price go down, it's buy point, selling here get 0 profit, meaningless. if price go up, it's sell point, won't buy. buy2 must happen before sell1, because if not, buy2 will be negative, won't update.
Fibonacci numbers,斐波那契数列问题
Staircase,爬楼梯问题
House thief,偷房子问题
Equal Subset Sum Partition,相等子集划分问题
Subset Sum,子集和问题
Minimum Subset Sum Difference,子集和的最小差问题
Other,其它
Coin Change,换硬币问题
Others,其它
Math,数学相关
Buy and Sell Stock,股票买卖问题
Paint House,粉刷房子问题
Job Schedule,工作计划问题
Minimum Number of Operations,最少操作次数问题
Intervals Merge,区间合并
Triangulation,三角剖分
Rectangle Segmentation,矩形分割
Longest Common Substring,最长公共子串
Longest Common Subsequence,最长公共子序列
Longest Increasing Subsequence,最长上升子序列
Shortest Common Super-sequence,最短公共超级子序列
Others,其它
Longest Palindromic Subsequence,最长回文子序列
Longest Palindromic Substring,最长回文子字符串
Count Palindromic Subsequences/Substrings,回文子序列/子字符串的个数
Palindromic Partitioning,回文分割
Divide & conquer, solve with 2 pass: order and reversed order
LIS problem
局部最优和全局最优
these problems are not DP, but there ideas are similar: solving subproblem.
it's not only one subproblem, instead, many subproblems need to be compared or processed.
most game problem
3 for-loop -> DFS + Memo
(Easy)
、(简单)
(Easy)
、(简单)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(hard)
、(困难)
(hard)
、(困难)
(Easy)
、(简单)
(Easy)
、(简单)
(Easy)
、(简单)
(Easy)
、(简单)
(Easy)
、(简单)
(Medium)
、(中等)
Medium
、中等
Hard
、困难
Hard
、困难
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Hard)
、(困难)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Hard)
、(困难)
(Medium)
、(中等)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Hard)
、(困难)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Hard)
、(困难)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Hard)
、(困难)
(Hard)
、(困难)
(Easy)
、(简单)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Easy)
、(简单)
(Easy)
、(简单)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Hard)
、(困难)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Hard)
、(困难)
(Easy)
、(简单)
(Medium)
、(中等)
(Medium)
、(中等)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Medium)
、(中等)
(Hard)
、(困难)
(Medium)
、(中等)
(Hard)
、(困难)
(Medium)
、(中等)
(Medium)
、(中等)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Medium)
、(中等)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Medium)
、(中等)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(Hard)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)
(Hard)
、(困难)