1. 基本动态规划【上台阶和抢劫问题】
题目要求：
- 给定 n 节台阶，每次可以走一步或走两步，求一共有多少种方式可以走完这些台阶。
解析：因为dp[i] 只与dp[i-1] 和dp[i-2] 有关：
- 因此可以只用两个变量来存储dp[i-1] 和dp[i-2]，
- 使得原来的 O(n)空间复杂度优化为 O(1)复杂度。
def climbstairs(len):
dp = 0
dp1 = 1
dp2 = 2
if len <= 2:
return len
for i in range(2, len):
dp = dp1 + dp2
dp1 = dp2
dp2 = dp
return dp
题目要求：
- 假如你是一个劫匪，并且决定抢劫一条街上的房子，每个房子内的钱财数量各不相同。
- 如果你抢了两栋相邻的房子，则会触发警报机关。
- 求在不触发机关的情况下最多可以抢劫多少钱。
def rob(arr):
length = len(arr)
dp = 0
dp1 = 0
dp2 = 0
if length == 0:
return 0
if length == 1:
return arr[0]
for i in range(0, length):
dp = max(dp2 + arr[i], dp1)
dp2 = dp1
dp1 = dp
return dp
2. 背包问题【0-1背包和完全背包】
0-1背包问题:
- dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值
- 我们不将物品 i 放入背包，那么dp[i][j] = dp[i-1][j]
- 如果我们将物品 i 放入背包，假设第 i 件物品体积为 w，价值为 v，那么我们得到 dp[i][j] = dp[i-1][j-w] + v
- 我们只需在遍历过程中对这两种情况取最大值即可
- 假设我们目前考虑物品 i = 2，且其体积为w = 2，价值为v = 3；
- 对于背包容量 j，我们可以得到dp[2][j] = max(dp[1][j], dp[1][j-2] + 3)。
def knapsack(weights, values, N, W):
"""
0-1背包对物品的迭代放在外层，里层的体积或价值逆向遍历
完全背包对物品的迭代放在里层，外层的体积或价值正向遍历
:param weights: 物品的重量数组
:param values: 物品的价值数组
:param N: 物品的个数
:param W: 背包的最大承受重量
:return:
"""
dp = [0] * (W + 1) # dp数组用来存储物品的最大价值,dp[i-1] 前 i-1 个物品的最大价值.
for i in range(1, N + 1): # 遍历前 i 个物品
w = weights[i - 1]
v = values[i - 1]
for j in range(W, w - 1, -1): # 这里,dp[j]需要满足的最大重量 j >= W-w, range()为左开右闭区间，所以需要: w-1
dp[j] = max(dp[j], dp[j - w] + v)
return dp[W]
完全背包问题
def knapsack2(weights, values, com_N, com_W): # 完全背包
"""
用动态规划来解决背包问题:
完全背包问题的状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v
:param weights: 物品的重量数组
:param values: 物品的价值数组
:param com_N: 物品的个数
:param com_W: 背包的最大承受重量
:return:
"""
dp = [[0] * (com_W + 1)] * (com_N + 1)
for i in range(1, com_N + 1): # 遍历前 i 个物品
w = weights[i - 1]
v = values[i - 1]
for j in range(1, com_W + 1):
if j >= w:
dp[i][j] = max(dp[i - 1][j], dp[i][j - w] + v)
else:
dp[i][j] = dp[i - 1][j]
return dp[com_N][com_W]
def knapsack3(weights, values, com_N, com_W): # 完全背包
"""
:param weights: 物品的重量数组
:param values: 物品的价值数组
:param com_N: 物品的个数
:param com_W: 背包的最大承受重量
:return:
"""
dp = [0] * (com_W + 1)
for i in range(1, com_N + 1): # 遍历前 i 个物品
w = weights[i - 1]
v = values[i - 1]
for j in range(w, com_W + 1):
dp[j] = max(dp[j], dp[j - w] + v)
return dp[com_W]
3. 字符串【字符串匹配和最长子序列】
字符串匹配(非动态规划)，详细解析参考：Implement strStr()
- 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1
Input: haystack = "hello", needle = "ll"
Output: 2
Input: haystack = "aaaaa", needle = "bba"
Output: -1
def find_substr(string, substring):
fri_index = string.find(substring, 0, len(string))
last_index = string.rfind(substring) # 0, len(string)默认
return fri_index, last_index
if __name__ == '__main__':
s = "this is string example....wow!!!"
subs = "is"
fri, last = find_substr(s, subs)
print("fri = {} last = {}".format(fri, last))
输出
fri = 2 last = 5
public int strStr(String haystack, String needle) {
if (needle.isEmpty()) return 0;
int sizeA = haystack.length(), sizeB = needle.length();
for (int i = 0; i <= sizeA - sizeB; i++) {
if (haystack.substring(i, i + needle.length()).equals(needle))
return i;
}
return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String_Solution solution = new String_Solution();
String string = "aaaaa";
String string2 = "bba";
int bool = solution.strStr(string, string2);
System.out.println(bool);
}
// indexOf 字符串中查找其子串第一次出现的位置,如果没有找到该子串,则返回-1
public int strStr2(String haystack, String needle) {
int index=haystack.indexOf(needle);
return index;
}
最长公共子序列：(Longest Common Subsequence)
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
解析：
- 最长公共子序列，即两个序列 X 和 Y 的公共子序列中，长度最长的那个，
公共子序列不同于公共字串，公共子序列可以是不连续的，但是前后位置不变。
通过上图，我们可看出：两个序列的最长公共子序列的状态转移方程
d
p
[
i
]
[
j
]
=
{
d
p
[
i
?
1
]
[
j
?
1
]
+
1
，
i
f
：
i
=
j
m
a
x
(
d
p
[
i
?
1
]
[
j
]
,
d
p
[
i
]
[
j
?
1
]
)
，
i
f
：
i
≠
j
\begin{equation*} dp[i][j]=\begin{cases} dp[i - 1][j - 1] + 1，if：i=j\\ max(dp[i - 1][j], dp[i][j - 1])，if：i \neq j \end{cases} \end{equation*}
dp[i][j]={dp[i?1][j?1]+1，if：i=jmax(dp[i?1][j],dp[i][j?1])，if：i=j??
def longest_common_subsequence(text1, text2):
m = len(text1)
n = len(text2)
dp = [[0] * (n + 1)] * (m + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
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])
return dp[m][n]
if __name__ == '__main__':
text = "acbde"
text0 = "ace"
value = longest_common_subsequence(text, text0)
print(value)
str1 = "abcbdab"
str2 = "bdcaba"
value2 = longest_common_subsequence(str1, str2)
print(value2)
输出：
3
4
4. 分割类问题【完全平方数相加】
完全平方数相加
- 题目：
- 给定一个正整数，求其最少可以由几个完全平方数相加构成。
- 解析
- 对于
分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割条件的位置。 - 我们定义一个一维矩阵dp，其中dp[i] 表示数字i 最少可以由几个完全平方数相加构成。
- 在本题中，位置i 只依赖 i ? k 2 i - k^2 i?k2 的位置，如 i - 1、i - 4、i - 9 等等，才能满足完全平方分割的条件。
- 因此dp[i] 可以取的最小值即为
1 + min(dp[i-1], dp[i-4], dp[i-9] ...)。
- 对于
Python代码
def num_squares(key):
dp = [99] * (key + 1) # 这里,99代指最大个数。
dp[0] = 0
for i in range(1, key + 1):
for j in range(1, i):
if j * j <= i: # 此处，展现的python中for循环的劣势
dp[i] = min(dp[i], dp[i - j * j] + 1)
else:
break
return dp[key]
print(num_squares(5))
java代码
import java.util.Arrays;
public class Solution {
public int numSquares(int n) {
int dp[] = new int[n+1];
/*
* 通过Arrays.fill方法就可以为每个元素赋予同样的值
* Arrays.fill(arr, 0, 2, 10);
* 0-2,不包括2的索引,打印的是10
*/
Arrays.fill(dp, 99);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j*j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i-j*j] + 1);
}
}
return dp[n];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int n = 5;
Solution solution = new Solution();
System.out.println(solution.numSquares(n));
}
}
输出：
2
5. 股票交易
股票交易类问题通常可以用动态规划来解决。对于稍微复杂一些的股票交易类问题，比如需要冷却时间或者交易费用，则可以用通过动态规划实现的状态机来解决。
1. Best Time to Buy and Sell Stock
题目描述
- 给定一段时间内每天的股票价格，已知你只可以买卖各一次，求最大的收益。
题解
- 我们可以遍历一遍数组，在每一个位置 i 时，记录 i 位置之前所有价格中的最低价格，
- 然后将当前的价格作为售出价格，查看当前收益是不是最大收益即可。
def max_profit(prices):
sell = 0
buy = -99 # 表示最小值
for i in range(0, len(prices)):
buy = max(buy, -prices[i])
sell = max(sell, buy + prices[i])
return sell
2. Best Time to Buy and Sell Stock IV
题目描述
- 给定一段时间内每天的股票价格，已知你只
可以买卖各 k 次，且每次只能拥有一支股票，求最大的收益。
题解
- 如果
k 大约总天数，那么我们一旦发现可以赚钱就进行买卖。 - 如果
k 小于总天数，我们可以建立两个动态规划数组 buy 和sell，对于每天的股票价格，buy[j] 表示在第 j 次买入时的最大收益，sell[j] 表示在第 j 次卖出时的最大收益。
def max_profit_unlimited(prices):
"""
辅助函数，
:param prices:每天的股票价格
:return: maxprofit 最大收益
"""
maxprofit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
maxprofit += prices[i] - prices[i - 1]
return maxprofit
def max_profit2(k, prices):
days = len(prices)
if days < 2: # 天数小于2，买入后无法卖出，收益为 0
return 0
if k >= days: # 如果 k 大约总天数，那么我们一旦发现可以赚钱就进行买卖
return max_profit_unlimited(prices)
sell = [0] * (k + 1)
buy = [-99] * (k + 1) # 表示最小值
for i in range(0, days):
for j in range(1, k+1):
buy[j] = max(buy[j], sell[j-1] - prices[i])
sell[j] = max(sell[j], buy[j] + prices[i])
return sell[k]
3. Best Time to Buy and Sell Stock with Cooldown (Medium)
题目描述
- 给定一段时间内每天的股票价格，已知每次卖出之后必须冷却一天，且每次只能拥有一支股票，求最大的收益。
题解
- 我们可以使用
状态机来解决这类复杂的状态转移问题，通过建立多个状态以及它们的转移方式，我们可以很容易地推导出各个状态的转移方程。
def max_profit3(prices):
"""
给定一段时间内每天的股票价格，已知每次卖出之后必须冷却一天，且每次只能拥有一支股票，求最大的收益。
:param prices:
:return:
"""
days = len(prices)
if days == 0:
return 0
buy = [0] * days
sell = [0] * days
s1 = [0] * days
s2 = [0] * days
s1[0] = buy[0] = -prices[0]
for i in range(1, days):
buy[i] = s2[i - 1] - prices[i]
s1[i] = max(buy[i - 1], s1[i - 1])
sell[i] = max(buy[i - 1], s1[i - 1]) + prices[i]
s2[i] = max(s2[i - 1], sell[i - 1])
return max(sell[days - 1], s2[days - 1])
本笔记参考：LeetCode 101: A LeetCode Grinding Guide (C++ Version)
特此感谢作者高畅Chang Gao的技术支持