在开始这个话题之前, 让我先介绍一下自己. 我是一名移动开发者, 目前在华沙工作, 利用业余时间为面试做准备. 两年前我就开始准备面试了.
在那个时候, 我应该说我不能解决两个和的问题. 在我看来, 简单的问题就像困难的问题一样, 所以大多数时间我不得不看社论和讨论部分.
目前, 我已经解决了约 800 个问题, 并经常参加比赛. 我通常在比赛中解决 3 个问题, 有时 4 个问题. 好的, 我们回到话题上来.
最近我把注意力集中在动态规划上, 因为它是面试准备中最难的话题之一.
在DP中解决了140个问题之后, 我发现在不同的问题中可以找到的模式很少. 所以我做了一个研究, 找到了以下的主题.
我不会给出完整的方法来解决问题, 但这些模式可能有助于你解决DP问题.
这类问题模式的定义:
Given a target find minimum (maximum) cost / path / sum to reach the target.
给定目标并寻达到目标的最短(或最大)开销/路径/和
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]
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
这类问题模式的定义:
Given a target find a number of distinct ways to reach the target.
给定目标, 找出不同的方法来达到目标.
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]
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; }
有些问题需要指出重复的次数, 在这种情况下, 可以增加一个循环来模拟每次的重复.
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 Medium
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
这类问题模式的定义:
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.
给定一组数字, 考虑到当前的数字和你能从左边和右边得到的最好的结果, 找到问题的最优解.
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]
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
这种模式的描述可能会有所不同, 但大多数情况下, 给定的两个字符串的长度并不大.
Given two strings s1 and s2, return some result.
给定两个字符串s1和s2, 返回一些结果.
Most of the problems on this pattern requires a solution that can be accepted in O(n^2) complexity.
这种模式中的大多数问题都有小于 O(n^2) 复杂度的解.
// 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
如果只给定一个字符串 s, 解法变化不大.
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
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.
这种问题的某些中间解一般是可以舍弃的.需要根据情况决定是否使用当前状态. 所以, 这个问题需要你在当前的状态下做出决定.
Given a set of values find an answer with an option to choose or ignore the current value.
给定一组值, 通过选择或忽略当前值, 来得出最终解.
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
希望本文对你有所帮助.