斐波拉契数列
“斐波拉契数列”问题是认识动态规划非常好的例子。
LeetCode 第 70 题：Climbing Stairs
提示：斐波拉契数列，画出树形结构，发现大量重叠子问题，所以用动态规划。
LeetCode 第 120 题：Triangle
提示：状态 + 状态转移方程。
Python 代码：
class Solution:
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
l = len(triangle)
if l == 0:
return 0
dp = triangle[-1]
for i in range(l - 2, -1, -1):
for j in range(len(triangle[i])):
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
return dp[0]
LeetCode 第 64 题 ：Minimum Path Sum 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
提示：状态 + 状态转移方程。也可以用组合数来做。
LeetCode 第 343 题： Integer Break
提示：关键在“将其拆分为至少两个正整数的和”，还可以使用贪心算法。
Python 代码：
class Solution:
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
product = [0] * (n + 1)
product[1] = 1
for i in range(2, n + 1):
product_max = 0
for j in range(1, i):
product_max = max(j * product[i - j], product_max, j * (i - j))
product[i] = product_max
return product[n]
LeetCode 第 279 题：完全平方数（特别重要）
传送门：279. 完全平方数。提示：1、BFS；2、动态规划，状态就是题目中要问的问题。
Python 代码：
LeetCode 第 91 题：解码方法（特别重要）
提示：注意数组下标越界问题。
class Solution:
def numDecodings(self, s):
l = len(s)
if l == 0:
return 0
if l == 1:
return 1 if s[0] != '0' else 0
dp = [0 for _ in range(l)]
dp[0] = 1 if s[0] != '0' else 0
for i in range(1, l):
if s[i] != '0':
# 如果不是 '0' ，那么 s[i] 就可以编码，所以 cur 就至少是 dp[i-1]
dp[i] += dp[i - 1]
if 9 < int(s[i - 1:i + 1]) < 27:
# 可以和前面的数字组成一个编码
if i - 2 < 0:
# 12
dp[i] += 1
else:
dp[i] += dp[i - 2]
return dp[l - 1]
不同的路径
LeetCode 第 62 题：不同路径
提示：还可以用组合数公式。
LeetCode 第 63 题：不同路径 II
提示：分类讨论。
打家劫舍系列
LeetCode 第 198 题：House Robber
提示：状态转移，如果使用“滚动数组”，可以把空间复杂度降到 。
Python 代码：掌握“滚动数组”的写法
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size == 0:
return 0
if size <= 2:
return max(nums)
pre = nums[0]
cur = max(nums[0], nums[1])
for i in range(2, size):
temp = cur # 因为 cur 会被覆盖，所以先把 cur 存一下，最后再赋值给 pre
cur = max(cur, pre + nums[i])
pre = temp
return cur
LeetCode 第 213 题：House Robber II
提示：基于上一个问题。
LeetCode 第 337 题：House Robber III
提示：递归求解，先写递归终止条件。
Java 代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rob(TreeNode root) {
if (root == null) {
return 0;
}
int val = root.val;
if(root.left != null){
val+= rob(root.left.left) + rob(root.left.right);
}
if(root.right != null){
val+= rob(root.right.left) + rob(root.right.right);
}
return Math.max(val, rob(root.left) + rob(root.right));
}
}
LeetCode 第 309 题：Best Time to Buy and Sell Stock with Cooldown
（状态机解决）
背包问题—— Knapsack01（6题）
LeetCode 第 416 题：分割等和子集
提示：0-1 背包问题，思路是：物品一个一个加进来。
状态：dp[i][j]：考虑索引是 [0,i] 这个区间的物品是否能够填充容量为 j 的背包。
Python 代码：这是用二维数组的写法，试试看能不能用一维数组写出来
class Solution:
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
l = len(nums)
if l == 0:
return False
s = sum(nums)
half = s // 2
if s % 2 == 1:
return False
dp = [[0 for _ in range(half + 1)] for _ in range(l)]
# 先填第 1 行，即 nums[0] 这个物品，是不是能够填满 0，1，。。。，half 的背包
for i in range(half + 1):
dp[0][i] = False if nums[0] != i else True
# 再填后面几行
for i in range(1, l):
for j in range(half + 1):
# 不放这个物品 、 放这个物品
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
return dp[-1][-1]
LeetCode 第 322 题 ：Coin Change
提示：抓住“你可以认为每种硬币的数量是无限的”。
Python 代码：掌握 BFS 的写法，关键是画图，还有里面的入队逻辑不能错，同类问题还有完全平方数
class Solution:
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
# 特判 [2147483647]
# 2
if amount <= 0:
return 0
coins.sort()
if coins[0] > amount:
return -1
# 不要用数组，用哈希表
# marked = [False for _ in range(amount)]
marked = set()
queue = [(0, amount)]
while queue:
# print(queue)
level, top = queue.pop(0)
level += 1
for coin in coins:
residue = top - coin
if residue == 0:
return level
if residue > 0 and residue not in marked:
queue.append((level, residue))
marked.add(residue)
if residue < 0:
# 有了前面排序做保证
break
return -1
Java 代码：动态规划
public class Solution {
public int coinChange(int[] coins, int amount) {
int len = coins.length;
if (amount == 0) {
return 0;
}
if (coins == null || len == 0) {
return -1;
}
// 要把 0 算进去，这是基本情况，所以开辟 coins 这么多空间的
// 组成当前的总价值需要的最少硬币数
int[] dp = new int[amount + 1];
// dp 问题的套路，把初值先算出来，因为递归到底的时候，可能到这个地方
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
int minCount = Integer.MAX_VALUE;
for (int j = 0; j < coins.length; j++) {
if (i - coins[j] >= 0 && dp[i - coins[j]] != -1) {
minCount = Integer.min(dp[i - coins[j]] + 1, minCount);
}
}
dp[i] = minCount == Integer.MAX_VALUE ? -1 : minCount;
}
return dp[amount];
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] coins = {1};
int amount = 0;
int coinChange = solution.coinChange(coins, amount);
System.out.println(coinChange);
}
}
LeetCode 第 377 题 ：Combination Sum IV
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
Java 代码：
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
// 这一步很关键，想想为什么 dp[0] 是 1
// 因为 0 表示空集，空集和它"前面"的元素凑成一种解法，所以是 1
// 这一步要加深体会
dp[0] = 1;
for (int i = 1; i < target + 1; i++) {
for (int num : nums) {
if (i >= num) {
dp[i] = dp[i] + dp[i - num];
}
}
}
return dp[target];
}
}
Java 代码：
public int combinationSum4(int[] nums, int target) {
int[] memo = new int[target + 1];
memo[0] = 1;
for (int i = 0; i < target; i++) {
for (int num : nums) {
if (i + num <= target) {
memo[i + num] += memo[i];
}
}
}
return memo[target];
}
LeetCode 第 474 题：Ones and Zeroes
提示：二维背包问题，数组有三维，可以降到一维。
LeetCode 第 139 题：Word Break（重点）
提示：用“记忆化递归”和“动态规划”都做一下。先把单词列表放到哈希表里，然后先判处。
LeetCode 第 494 题：Target Sum
传送门：494. 目标和。
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号
+和-。对于数组中的任意一个整数，你都可以从+或-中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3 输出: 5 解释: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 一共有5种方法让最终目标和为3。注意:
- 数组的长度不会超过20，并且数组中的值全为正数。
- 初始的数组的和不会超过1000。
- 保证返回的最终结果为32位整数。
提示：1、回溯；2、0-1 背包问题。要处理一些细节。
例题1：LeetCode 第 300 题：Longest Increasing Subsequence
提示：1、动态规划；2、使用二分法。
练习1：LeetCode 第 376 题：Wiggle Subsequence
提示：1、状态机；2、贪心；
最长公共子序列问题（Longest Common Sequence）
地下城游戏（困难）
最长连续子数组的和
《编程之法》 P10 字典排序
看看哪里用到了“滚动数组”的技巧，典型的一维动态规划问题
分割回文串问题
LeetCode 第 131 题：分割回文串1：dfs 或者动态规划
LeetCode 第 132 题：分割回文串2（困难）：动态规划
LeetCode 第 62 题：最短的唯一路径（1）
思路：典型的动态规划问题。用一维的空间复杂度就可以写出来。
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
if m == 0:
return 0
dp = [1] * n
for row in range(m - 1):
for col in range(1, n):
dp[col] += dp[col-1]
return dp[-1]
LeetCode 第 63 题：最短的唯一路径（2）
思路：典型的动态规划问题。用一维的空间复杂度就可以写出来。
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m = len(obstacleGrid)
if m == 0:
return 0
n = len(obstacleGrid[0])
if obstacleGrid[0][0] == 1:
return 0
dp = [0] * n
# 这一步不要忘记了
dp[0] = 1
# 再写后面几行
for row in range(m):
for col in range(n):
# 【就分下面这两种情况就可以了】
if obstacleGrid[row][col] == 1:
dp[col] = 0
elif col > 0:
dp[col] += dp[col - 1]
else:
# 第 0 列不是 0 就是 1
# 0 的情况首先判断了
# 什么都不做
pass
return dp[-1]
LeetCode 第 64 题：路径和最小
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
for col in range(1, n):
# 第 0 行特殊处理，不要忘记了
grid[0][col] += grid[0][col - 1]
for row in range(1, m):
grid[row][0] += grid[row - 1][0]
for col in range(1, n):
grid[row][col] += min(grid[row - 1][col], grid[row][col - 1])
return grid[-1][-1]
LeetCode 第 115 题：不同的子序列（困难）
传送门：115. 不同的子序列。
要求：给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
分析：首先，空串就是 1 种情况。
使用二维动态规划。状态：到目前为止匹配的种数。
- 这是一道典型的动态规划问题，并且还是二维的动态规划问题
- 而且这个状态还比较难想，要结合具体的例子才能找到状态转移方程
- 首先要注意到最特殊的情况：当 t == "" 为 true 的时候，不论 s 是什么，s 都有一个子串（那就是空字符串）能和此时的 t 匹配。
- 因此
dp[i][0] = 1，所以0这个位置就被占据了，这就是为什么 dp 要设置成dp[slen + 1][tlen + 1]的原因。
参考资料：
https://leetcode.com/problems/distinct-subsequences/discuss/37320/Java-.
https://www.cnblogs.com/higerzhang/p/4133793.html
https://www.jianshu.com/p/510906b900ec
public class Solution2 {
public int numDistinct(String s, String t) {
int slen = s.length();
int tlen = t.length();
if (slen == 0 || tlen == 0) {
return 0;
}
int[][] dp = new int[slen + 1][tlen + 1];
for (int i = 0; i < slen; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < slen + 1; i++) {
for (int j = 1; j < tlen + 1; j++) {
dp[i][j] = dp[i - 1][j];
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return dp[slen][tlen];
}
public static void main(String[] args) {
String s = "babgbag";
String t = "bag";
Solution2 solution = new Solution2();
int numDistinct = solution.numDistinct(s, t);
System.out.println(numDistinct);
}
}
（本节完）
