之前写过一篇关于 DP 文章，总结了几种常见的动态规划问题。（传送门）
今天去了华为面试（3轮），每一轮都让手写一道算法题（都是动态规划的） ，不得不说现在的招聘要求真的是“水涨船高”（保研也是）。上半年去面实习生的时候，只有两轮面试，都没要求写算法题。可能是打了一波贸易战，坑位少了，自然要求也高。也不知道程序员的“热钱”还能恰多久，希望能赶在寒冬来临之前恰个饱饭。
现在写下这几道题的总结，希望对后人有帮助。
Rod Cutting
棍棒切割问题。
给定一段长度为 (n) 的的棍棒，和一个价格表 (p_i (i=1,...,n)) , (p_i) 表示长度为 (i) 的棍棒的价格。 求如何切割长度为 (n) 的棍棒，使得价格最大，求最大价格。
例如，给出价格表如下：
| 长度 (i) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 价格 (p_i) | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
现在给定 (n=3) 的棍棒，切割位置有 2 处，那么切割方案有 $2^{2-1} = 2 $ 种：
- 3 = 0 +3：价格为 8
- 3 = 1 + 2：价格为 6
显然，对于任意的 (n) ，可切割位置为 (n-1) 个，所以切割方案有 $frac {2^{n-1}} {2} $ 种，因此如果是穷举，复杂度达到 (O(2^n)) 。
现在考虑使用动态规划的解法。
令 dp[i] 表示 长度为 (i) 的棍棒的最大价格。
状态转移方程：
需要注意的 2 个地方：
price[0] = 0dp数组的大小是n+1
Python实现：
import sys
'''
dp[i]表示：长度 i 的 rod 能够获得的最大利润
dp[0] = price[0] = 0
dp[1] = price[1]
dp[i] = max(dp[i-j]+price[j]),1<=j<=i
'''
prices = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
def rodCutting(size: int, prices: list) -> int:
dp = [0 for i in range(0, size+1)]
for i in range(0, size+1):
dp[i] = prices[i]
for j in range(1, i):
dp[i] = max(dp[i], dp[i - j] + prices[j])
print(dp)
return dp[size]
print(rodCutting(4, prices))
GetNextLarge
后来发现好像是 Leetcode 上面的一道题。
给定一个链表, 输出每个节点，在它后面的第一个不小于它的节点，不存在则是-1。
Sample:
Input: [1,5,6,0,1,5,8]
Output:[5,6,8,1,5,8,-1]
暴力解法：(O(N^2)) ，需要给出 (O(N)) 的解法（当时写了个暴力法，面试官提示有 (O(N)) 的解法，但是没答出来，还好还是过了这一轮面试）。
一种解法是利用栈：从前往后扫描这个链表，每扫描一个节点，节点元素 val 压栈，进栈的条件是 val < s.top，否则（也就是 s.top <= val）该节点的 val 就是 s.top 的 next large value。（也就是说，整个过程中，从 bottom 到 top ，栈是呈降序排列的）
C++代码 ：
vector<int> getNextLarge(int a[], int len)
{
stack<int> s;
vector<int> v(len, -1);
for (int i = 0; i < len - 1; i++)
{
if (s.empty() || a[i] < a[s.top()])
s.push(i);
else
{
while (!s.empty() && a[s.top()] < a[i])
{
int x = s.top();
s.pop();
v[x] = a[i];
}
s.push(i);
}
}
return v;
}
int main()
{
int a[] = {1, 3, 1, 8, 9, 3, 1, 8, 1, 7, 1};
auto v = getNextLarge(a, 11);
for (int i = 0; i < 11; i++)
cout << setw(4) << a[i];
cout << endl;
for (auto x : v)
cout << setw(4) << x;
}
最小路径和
给定一个 (n×n) 的二维数组，求出从 (0,0) 到 (n-1,n-1) 的路径中，有一个和最小的路径，给出最小和。
例如：
[1, 2, 3]
[4, 9, 2]
[1, 2, 1]
最小的路径是：
1->2->3->2->11->4->1->2->1
树塔问题的变种，求出具体的路径也不难（开一个二维数组记录路径即可），在这里给出求最小和的DP解法。
令 dp[i, j] 表示从 (i,j) 到 (n-1,n-1) 的最小路径和。
边界条件：
状态转移方程：
Python代码实现：
n = 3
plat = [
[1, 2, 3],
[4, 9, 2],
[1, 2, 1]
]
dp = [[0 for i in range(3)] for i in range(3)]
dp[n - 1][n - 1] = plat[n - 1][n - 1]
for i in reversed(range(0, n - 1)):
dp[i][n - 1] = plat[i][n - 1] + dp[i + 1][n - 1]
for j in reversed(range(0, n - 1)):
dp[n - 1][j] = plat[n - 1][j] + dp[n - 1][j + 1]
for i in reversed(range(0, n - 1)):
for j in reversed(range(0, n - 1)):
dp[i][j] = plat[i][j] + min(dp[i + 1][j], dp[i][j + 1])
print(dp[0][0])
最长公共子串
这是 LCS 的变种。
最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别： 子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续。
最长公共子序列的解法，请看这里。
例如给出：
string s1 = "abcde";
string s2 = "abde";
要求出最大公共子串的长度，显然这里答案是 2 （"ab" 或者 "de"）。
当时我就无脑写了个 dp 给了面试官，结果那个面试官好像⑧太懂算法，我现场手动算了一个例子给他看，他好像还是⑧懂，也不知道记录我做没做对。（可能这题想考基本功，面试官想听暴力穷举法的思路）
令 (dp[i,j]) 表示以 (s1[i]) 结尾的，且以 (s2[j]) 结尾的最大公共子串的长度。
因为“子串”要求是连续的，所以在状态定义时大多数都是定义为“以XX结尾”，这样才能保证连续。
边界条件：
状态转移方程：
Python实现：
s1, s2 = "abcde", "abde"
# s1, s2 = "aaaaaaaaaa", "aaaa"
# s1, s2 = "helloworld", "hellohelloworldhello"
def solve(s1: str, s2: str) -> int:
len1 = len(s1)
len2 = len(s2)
dp = [[0 for i in range(0, len2 + 1)] for i in range(0, len1 + 1)]
maxlen = 0
for i in range(1, len1+1):
for j in range(1, len2+1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = 0
# dp[i][j] = max(dp[i-1][j], dp[i][j-1]) #最长公共子序列
maxlen = max(maxlen, dp[i][j])
return maxlen
print(solve(s1, s2))