动态规划（DP）确实是一个难点。因为相对其他方面来说，DP也练得最少。加上坊间都在传，DP很难，就吓退了很多人吧。

虽然DP确实五花八门，想找一套普遍适用的方法是没有的。

但DP也就是解决编程问题的一种，见得多了，也就知道需要用DP来解了。无他，唯手熟尔。

举例来说，大部分学过一点DP的人，都知道要用DP来解斐波那契数列。原因大家也都知道，就是通过空间换时间，通过开销额外的空间，去降维时间复杂度。

其他的DP题也都是一样的思路，所以，先通过简单的例子入手，理解几个题目之后。就会发现DP也是有规律可循的了。

我在下面就列举三个对我有启发的资料吧！

希望对你也有帮助，如果有帮助，麻烦点赞，毕竟这也是我进一步写作的动力。

第一个资料，来自LeetCode去年圣诞节大奖的第一名，为了方便大家阅读，我把内容拷贝过来，放在分割线之间了，大家可以去看原文，还能看到原文下面的很多很有参考价值的评论。

原文作者：aatalyk

原文出处：LeetCode Discuss

原文链接：https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns

原文是英文写的，我觉得大家学编程，掌握基本的英文是必须的，我就不全文翻译啦。我会在关键的地方加上注释。

Before starting the topic let me introduce myself. I am a Mobile Developer currently working in Warsaw and spending my free time for interview preparations. I started to prepare for interviews two years ago. At that time I should say I could not solve the two sum problem. Easy problems seemed to me like hard ones so most of the time I had to look at editorials and discuss section. Currently, I have solved ~800 problems and time to time participate in contests. I usually solve 3 problems in a contest and sometimes 4 problems. Ok, lets come back to the topic.

Recently I have concentrated my attention on Dynamic Programming cause its one of the hardest topics in an interview prep. After solving ~140 problems in DP I have noticed that there are few patterns that can be found in different problems. So I did a research on that and find the following topics. I will not give complete ways how to solve problems but these patterns may be helpful in solving DP.

Patterns，DP模式

原作者把DP的题目分成了五类：

Minimum (Maximum) Path to Reach a Target
Distinct Ways
Merging Intervals
DP on Strings
Decision Making

Minimum (Maximum) Path to Reach a Target，到底目标通过一条最大或是最小的条件路径

Generate problem statement for this pattern

Statement，一般这类问题具有下面类似的描述

Given a target find minimum (maximum) cost / path / sum to reach the target.

Approach，解题方法

Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state.

       routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]     

Generate optimal solutions for all values in the target and return the value for the target.

       for (int i = 1; i <= target; ++i) {    for (int j = 0; j < ways.size(); ++j) {        if (ways[j] <= i) {            dp[i] = min(dp[i], dp[i - ways[j]]) + cost / path / sum;        }    } }   return dp[target]     

Similar Problems，其他类似的问题还有：

746. Min Cost Climbing Stairs Easy

       for (int i = 2; i <= n; ++i) {    dp[i] = min(dp[i-1], dp[i-2]) + (i == n ? 0 : cost[i]); }   return dp[n]     

64. Minimum Path Sum Medium

       for (int i = 1; i < n; ++i) {    for (int j = 1; j < m; ++j) {        grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];    } }   return grid[n-1][m-1]     

322. Coin Change Medium

       for (int j = 1; j <= amount; ++j) {    for (int i = 0; i < coins.size(); ++i) {        if (coins[i] <= j) {            dp[j] = min(dp[j], dp[j - coins[i]] + 1);        }    } }     

931. Minimum Falling Path Sum Medium

983. Minimum Cost For Tickets Medium

650. 2 Keys Keyboard Medium

279. Perfect Squares Medium

1049. Last Stone Weight II Medium

120. Triangle Medium

474. Ones and Zeroes Medium

221. Maximal Square Medium

322. Coin Change Medium

1240. Tiling a Rectangle with the Fewest Squares Hard

174. Dungeon Game Hard

871. Minimum Number of Refueling Stops Hard

Distinct Ways，第二类DP问题，达到目标的不同方式总数

Generate problem statement for this pattern

Statement，问题描述

Given a target find a number of distinct ways to reach the target.

Approach，解题方法

Sum all possible ways to reach the current state.

       routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]     

Generate sum for all values in the target and return the value for the target.

       for (int i = 1; i <= target; ++i) {    for (int j = 0; j < ways.size(); ++j) {        if (ways[j] <= i) {            dp[i] += dp[i - ways[j]];        }    } }   return dp[target]     

Similar Problems，类似问题

70. Climbing Stairs easy

       for (int stair = 2; stair <= n; ++stair) {    for (int step = 1; step <= 2; ++step) {        dp[stair] += dp[stair-step];       } }     

62. Unique Paths Medium

       for (int i = 1; i < m; ++i) {    for (int j = 1; j < n; ++j) {        dp[i][j] = dp[i][j-1] + dp[i-1][j];    } }     

1155. Number of Dice Rolls With Target Sum Medium

       for (int rep = 1; rep <= d; ++rep) {    vector<int> new_ways(target+1);    for (int already = 0; already <= target; ++already) {        for (int pipe = 1; pipe <= f; ++pipe) {            if (already - pipe >= 0) {                new_ways[already] += ways[already - pipe];                new_ways[already] %= mod;            }        }    }    ways = new_ways; }     

Note，备注

Some questions point out the number of repetitions, in that case, add one more loop to simulate every repetition.

688. Knight Probability in Chessboard Medium

494. Target Sum Medium

377. Combination Sum IV Medium

935. Knight Dialer Medium

1223. Dice Roll Simulation Medium

416. Partition Equal Subset Sum Medium

808. Soup Servings Medium

790. Domino and Tromino Tiling Medium

801. Minimum Swaps To Make Sequences Increasing

673. Number of Longest Increasing Subsequence Medium

63. Unique Paths II Medium

576. Out of Boundary Paths Medium

1269. Number of Ways to Stay in the Same Place After Some Steps Hard

1220. Count Vowels Permutation Hard

Merging Intervals，第三类DP，区间合并

Generate problem statement for this pattern

Statement，问题描述

Given a set of numbers find an optimal solution for a problem considering the current number and the best you can get from the left and right sides.

Approach，解法方法

Find all optimal solutions for every interval and return the best possible answer.

       // from i to j dp[i][j] = dp[i][k] + result[k] + dp[k+1][j]     

Get the best from the left and right sides and add a solution for the current position.

       for(int l = 1; l<n; l++) {    for(int i = 0; i<n-l; i++) {        int j = i+l;        for(int k = i; k<j; k++) {            dp[i][j] = max(dp[i][j], dp[i][k] + result[k] + dp[k+1][j]);        }    } }   return dp[0][n-1]     

Similar Problems，类似问题

1130. Minimum Cost Tree From Leaf Values Medium

       for (int l = 1; l < n; ++l) {    for (int i = 0; i < n - l; ++i) {        int j = i + l;        dp[i][j] = INT_MAX;        for (int k = i; k < j; ++k) {            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + maxs[i][k] * maxs[k+1][j]);        }    } }     

96. Unique Binary Search Trees Medium

1039. Minimum Score Triangulation of Polygon Medium

546. Remove Boxes Medium

1000. Minimum Cost to Merge Stones Medium

312. Burst Balloons Hard

375. Guess Number Higher or Lower II Medium

DP on Strings，第四类DP，字符串上面的DP

General problem statement for this pattern can vary but most of the time you are given two strings where lengths of those strings are not big

Statement，问题描述

Given two strings s1 and s2, return some result.

Approach，解决方法

Most of the problems on this pattern requires a solution that can be accepted in O(n^2) complexity.

       // i - indexing string s1 // j - indexing string s2 for (int i = 1; i <= n; ++i) {    for (int j = 1; j <= m; ++j) {        if (s1[i-1] == s2[j-1]) {            dp[i][j] = /*code*/;        } else {            dp[i][j] = /*code*/;        }    } }     

If you are given one string s the approach may little vary

       for (int l = 1; l < n; ++l) {    for (int i = 0; i < n-l; ++i) {        int j = i + l;        if (s[i] == s[j]) {            dp[i][j] = /*code*/;        } else {            dp[i][j] = /*code*/;        }    } }     

1143. Longest Common Subsequence Medium

       for (int i = 1; i <= n; ++i) {    for (int j = 1; j <= m; ++j) {        if (text1[i-1] == text2[j-1]) {            dp[i][j] = dp[i-1][j-1] + 1;        } else {            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);        }    } }     

647. Palindromic Substrings Medium

       for (int l = 1; l < n; ++l) {    for (int i = 0; i < n-l; ++i) {        int j = i + l;        if (s[i] == s[j] && dp[i+1][j-1] == j-i-1) {            dp[i][j] = dp[i+1][j-1] + 2;        } else {            dp[i][j] = 0;        }    } }     

516. Longest Palindromic Subsequence Medium

1092. Shortest Common Supersequence Medium

72. Edit Distance Hard

115. Distinct Subsequences Hard

712. Minimum ASCII Delete Sum for Two Strings Medium

5. Longest Palindromic Substring Medium

Decision Making，第五类DP，取舍决定（当前元素取或是不取）

The general problem statement for this pattern is forgiven situation decide whether to use or not to use the current state. So, the problem requires you to make a decision at a current state.

Statement，问题描述

Given a set of values find an answer with an option to choose or ignore the current value.

Approach，解决方法

If you decide to choose the current value use the previous result where the value was ignored; vice-versa, if you decide to ignore the current value use previous result where value was used.

       // i - indexing a set of values // j - options to ignore j values for (int i = 1; i < n; ++i) {    for (int j = 1; j <= k; ++j) {        dp[i][j] = max({dp[i][j], dp[i-1][j] + arr[i], dp[i-1][j-1]});        dp[i][j-1] = max({dp[i][j-1], dp[i-1][j-1] + arr[i], arr[i]});    } }     

198. House Robber Easy

       for (int i = 1; i < n; ++i) {    dp[i][1] = max(dp[i-1][0] + nums[i], dp[i-1][1]);    dp[i][0] = dp[i-1][1]; }     

121. Best Time to Buy and Sell Stock Easy

714. Best Time to Buy and Sell Stock with Transaction Fee Medium

309. Best Time to Buy and Sell Stock with Cooldown Medium

123. Best Time to Buy and Sell Stock III Hard

188. Best Time to Buy and Sell Stock IV Hard

I hope these tips will be helpful

第二个材料，是下面这个LeetCode最近的帖子，列出了LC上面的DP的经典题目：

第三个，则是educative上面的DP课：

该门课程中, 作者将DP的问题分成以下几类:

1. 0/1 Knapsack, 0/1背包，6个题

0/1 Knapsack，0/1背包问题

Equal Subset Sum Partition，相等子集划分问题

Subset Sum，子集和问题

Minimum Subset Sum Difference，子集和的最小差问题

Count of Subset Sum，相等子集和的个数问题

Target Sum，寻找目标和的问题

2. Unbounded Knapsack，无限背包，5个题

Unbounded Knapsack，无限背包

Rod Cutting，切钢条问题

Coin Change，换硬币问题

Minimum Coin Change，凑齐每个数需要的最少硬币问题

Maximum Ribbon Cut，丝带的最大值切法

3. Fibonacci Numbers，斐波那契数列，6个题

Fibonacci numbers，斐波那契数列问题

Staircase，爬楼梯问题

Number factors，分解因子问题

Minimum jumps to reach the end，蛙跳最小步数问题

Minimum jumps with fee，蛙跳带有代价的问题

House thief，偷房子问题

4. Palindromic Subsequence，回文子系列，5个题

Longest Palindromic Subsequence，最长回文子序列

Longest Palindromic Substring，最长回文子字符串

Count of Palindromic Substrings，最长子字符串的个数问题

Minimum Deletions in a String to make it a Palindrome，怎么删掉最少字符构成回文

Palindromic Partitioning，怎么分配字符，形成回文

5. Longest Common Substring，最长子字符串系列，13个题

Longest Common Substring，最长相同子串

Longest Common Subsequence，最长相同子序列

Minimum Deletions & Insertions to Transform a String into another，字符串变换

Longest Increasing Subsequence，最长上升子序列

Maximum Sum Increasing Subsequence，最长上升子序列和

Shortest Common Super-sequence，最短超级子序列

Minimum Deletions to Make a Sequence Sorted，最少删除变换出子序列

Longest Repeating Subsequence，最长重复子序列

Subsequence Pattern Matching，子序列匹配

Longest Bitonic Subsequence，最长字节子序列

Longest Alternating Subsequence，最长交差变换子序列

Edit Distance，编辑距离

Strings Interleaving，交织字符串

大家可以先把以上35个题目练熟，这样DP到达中等水平肯定是okay了的。再加以训练和提高。突破算法的硬骨头不在话下。一定要按照三种方式对照起来练。

这个平台的介绍，看这个文章：

Happy Dynamic Programming!