# 动态规划模板

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

Minimum (Maximum) Path to Reach a Target-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.

1 | 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.

1 | for (int i = 1; i <= target; ++i) { |

### Similar Problems

746. Min Cost Climbing Stairs `Easy`

1 | for (int i = 2; i <= n; ++i) { |

64. Minimum Path Sum `Medium`

1 | for (int i = 1; i < n; ++i) { |

322. Coin Change `Medium`

1 | for (int j = 1; j <= amount; ++j) { |

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

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.

1 | 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.

1 | for (int i = 1; i <= target; ++i) { |

### Similar Problems

70. Climbing Stairs `easy`

1 | for (int stair = 2; stair <= n; ++stair) { |

62. Unique Paths `Medium`

1 | for (int i = 1; i < m; ++i) { |

1155. Number of Dice Rolls With Target Sum `Medium`

1 | for (int rep = 1; rep <= d; ++rep) { |

**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

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.

1 | // from i to j |

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

1 | for(int l = 1; l<n; l++) { |

### Similar Problems

1130. Minimum Cost Tree From Leaf Values `Medium`

1 | for (int l = 1; l < n; ++l) { |

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

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.

1 | // i - indexing string s1 |

If you are given one string

`s`

the approach may little vary

1 | for (int l = 1; l < n; ++l) { |

1143. Longest Common Subsequence `Medium`

1 | for (int i = 1; i <= n; ++i) { |

647. Palindromic Substrings `Medium`

1 | for (int l = 1; l < n; ++l) { |

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

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.

1 | // i - indexing a set of values |

198. House Robber `Easy`

1 | for (int i = 1; i < n; ++i) { |

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 😊

https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns