斐波那契数列
70. 爬楼梯
难度：简单
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
状态转移公式：f(n) = f(n-1) + f(n-2)。
public int climbStairs (int n) {
if (n == 1){
return 1;
}// 防止数组越界
int[] step = new int[n + 1];
step[1] = 1;
step[2] = 2;
for (int i = 3; i <= n; i++) {
step[i] = step[i - 1] + step[i - 2];
}
return step[n];
}
下面是空间复杂度优化过的代码。
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int pre2 = 1, pre1 = 2;
for (int i = 2; i < n; i++) {
int cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
198. 打家劫舍
难度：简单
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
废话不多说，我们直接走动态规划的流程。第一步就是寻找状态转移方程。
再重复一遍，状态转移矩阵是第N项与前若干项之间的关系。
现在我们是一个小偷，站在第i家的屋顶，我们是偷，还是不偷呢？这是个问题。
- 如果偷，那前面一家(i-1)我就不能偷，我当前偷到的最大值就是偷完前(i-2)家的最大值加上我偷这一家的钱。
- 如果不偷，我当前偷到的最大值就是偷完前(i-1)加的最大值，然后我就去下一家再看看。
所以状态转移矩阵就可以用如下一个公式表示：
rob(i) = Math.max( rob(i - 2) + currentHouseValue, rob(i - 1) )
第二步是利用状态转移矩阵自底向上求解问题。
我们定义一个数组dp[]，dp[i]是以第i个元素为结尾的偷窃到的最大金额。求dp[i]时，假设前面dp[0]~dp[i-1]都已经求出来了。
public int rob(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= nums.length; i++) {
dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i-1]);
}
return dp[nums.length];
}
下面是空间复杂度优化过的代码
public int rob (int[] nums) {
int pre1 = 0, pre2 = 0;
for (int i = 0; i < nums.length; i++) {
int cur = Math.max(pre1, pre2 + nums[i]);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
213. 打家劫舍 II
难度：中等
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
环形的处理，可以转换为比较[0, n-2]和[0, n-1]中谁能偷的比较多。
在某个区间内的偷窃金额的计算就和上题类似了。
public int rob(int[] nums) {
if (nums.length == 0 || nums == null) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
}
private int rob (int[] nums, int start, int end) {
int pre1 = 0, pre2 = 0;
for (int i = start; i <= end; i++) {
int cur = Math.max(pre1, pre2 + nums[i]);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
信件错排
题目描述：有 N 个 信 和 信封，它们被打乱，求错误装信方式的数量。
定义一个数组 dp 存储错误方式数量，dp[i] 表示前 i 个信和信封的错误方式数量。假设第 i 个信装到第 j 个信封里面，而第 j 个信装到第 k 个信封里面。根据 i 和 k 是否相等，有两种情况：
- i==k，交换 i 和 k 的信后，它们的信和信封在正确的位置，但是其余 i-2 封信有 dp[i-2] 种错误装信的方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-2] 种错误装信方式。
- i != k，交换 i 和 j 的信后，第 i 个信和信封在正确的位置，其余 i-1 封信有 dp[i-1] 种错误装信方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-1] 种错误装信方式。
综上所述，错误装信数量方式数量为：
dp[i] = (i-1)*dp[i-2]+(i-1)*dp[i-1]
母牛生产
题目描述：假设农场中成熟的母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量。
第 i 年成熟的牛的数量为：
dp[i] = dp[i-1] + dp[i-3]
矩阵路径
64. 最小路径和
难度：中等
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
使用一维动态规划，设置一个数组dp[n]，表示数组遍历到现在这个节点时，grid[0][0]到这一列的路径最小值。
为什么可以只用一维数组呢？我们可以考虑一下，对于不在左边界或上边界上的值，从原点到这个节点的路径最小值就是 原点到该节点左节点的路径最小值 和 原点到该节点上边的路径最小值 中的较小值，加上该节点的值。而原点到该节点左节点的路径最小值 实际上就是 dp[j-1], 原点到该节点上边的路径最小值 就是还没更新的dp[j]。
所以上面这个关系可以表示为：dp[j] = Math.min(dp[j - 1], dp[j])
public int minPathSum (int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (j == 0) {
dp[j] = dp[j];
} else if (i == 0) {
dp[j] = dp[j - 1];
} else {
dp[j] = Math.min(dp[j], dp[j - 1]);
}
dp[j] += grid[i][j];
}
}
return dp[n - 1];
}
62. 不同路径
难度：中等
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明： m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
二维解法：
状态转移方程
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1]
public int uniquePaths (int m, int n) {
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
matrix[i][0] = 1;
}
for (int j = 0; j < n; j++) {
matrix[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
}
}
return matrix[m - 1][n - 1];
}
下面是二维简化为一维的代码
dp[] 表示从起点到[*, j]的路径走法。
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
数组区间
303. 区域和检索 - 数组不可变
难度：简单
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
示例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:
- 你可以假设数组不可变。
- 会多次调用 sumRange 方法。
求区间 i ~ j 的和，可以转换为 sum[j + 1] - sum[i]，其中 sum[i] 为 0 ~ i - 1 的和。
状态转移方程：
sums[i] = sums[i-1] + nums[i-1]
class NumArray {
private int[] sums;
public NumArray(int[] nums) {
sums = new int[nums.length + 1];
for(int i = 1;i <= nums.length;i++){
sums[i] = sums[i-1] + nums[i-1];
}
}
public int sumRange(int i, int j) {
return sums[j+1] - sums[i];
}
}
413. 等差数列划分
难度：中等
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
如果满足以下条件，则称子数组(P, Q)为等差数组：
元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。
函数要返回数组 A 中所有为等差数组的子数组个数。
示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。
注意最后返回的结果不是 dp[n-1]，而是dp[] 所有的值加起来。
public int numberOfArithmeticSlices(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int n = A.length;
int[] dp = new int[n];
for (int i = 2; i < n; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = dp[i-1] + 1;
}
}
int count = 0;
for (int i : dp) {
count += i;
}
return count;
}
分割整数
343. 整数拆分
难度：中等
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
动态规划 + 暴力破解
所有组合都试一遍，找最大的
dp[i] 表示 i 拆出来的整数的最大乘积
状态转移方程（伪代码）：
dp[i] = max(dp[i], j * dp[i-j] , j*(i-j))
public int integerBreak (int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i - 1; j++) {
dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
}
}
return dp[n];
}
数学法
把一个整数分解成 3m + 2n这种形式时，乘积是最大的，证明如下：
答案是将任意数组字分为3m+2n时结果最大，并且尽可能多的3，剩余的值拆分为2。
这是因为，首先，如果对2，3进行拆分，2只有一种拆分方法就是1+1；3有两种拆分方法 1+2；1+1+1；
对于这两个数字，无论如何拆分得到的拆分单元的乘积均小于原始值；
而对于任意n>3, 拆分为两个数得到的乘积(n/2)^2 (n为偶数时)或 (n/2)((n+1)/2)*(n/2)（n为奇数时）均大于n;
因为对于函数y=(n/2)^2-n 或 (n/2)((n+1)/2)*(n/2)-n在n>3时均有y>0（且求导可发现在n>=3时单调递增）;
也就是说，当n>3时，对n进行拆分得到的数字的乘积一定大于原始值；
也就是说，2和3是该问题的最小不可分单元；
作者：LukeLee
链接：https://leetcode-cn.com/problems/two-sum/solution/c-99-shu-xue-zheng-ming-zui-you-jie-by-lukelee/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
public int integerBreak (int n) {
if (n == 2 || n == 3) {
return n - 1;
}
int ans = 1;
while (n > 4) {
ans *= 3;
n -= 3;
}
return ans * n;
}
279. 完全平方数
难度：中等
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
BFS 也可以做
dp[i] 表示 组成整数 i 的完全平方数的最少个数。
public int numSquares(int n) {
List<Integer> squares = generateSquares(n);
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (Integer square : squares) {
if (square > i) {
break;
}
min = Math.min(min, dp[i - square] + 1);
}
dp[i] = min;
}
return dp[n];
}
/**
* 生成小于 n 的平方数的序列
* @param n 目标数
* @return 1,4,9,...
*/
private List<Integer> generateSquares(int n) {
List<Integer> squares = new ArrayList<>();
int square = 1;
int diff = 3;
while (square <= n) {
squares.add(square);
square += diff;
diff += 2;
}
return squares;
}
91. 解码方法
难度：中等
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
dp[i]表示 前 i 个字母组成的子串能组成多少种解码方法。
注意一些边界条件的判断，比如首位是不是0，如果是两位数的话，是否在26以内。
public int numDecodings (String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; i++) {
int one = Integer.valueOf(s.substring(i - 1, i));
if (one != 0) {
dp[i] = dp[i] + dp[i - 1];
}
if (s.charAt(i - 2) == '0') {
continue;
}
int two = Integer.valueOf(s.substring(i - 2, i));
if (two <= 26) {
dp[i] = dp[i] + dp[i - 2];
}
}
return dp[n];
}
最长递增子序列
300. 最长上升子序列
难度：中等
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n^2^) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
已知一个序列 {S1, S2,…,Sn}，取出若干数组成新的序列 {Si1, Si2,…, Sim}，其中 i1、i2 … im 保持递增，即新序列中各个数仍然保持原数列中的先后顺序，称新序列为原序列的一个 子序列 。
如果在子序列中，当下标 ix > iy 时，Six > Siy，称子序列为原序列的一个 递增子序列 。
说人话：原序列取若干个数出来（不一定连续），如果这个子序列的元素是递增的话，就是递增子序列。
动态规划
状态转移方程为
dp[n] = max(1, dp[i] + 1)| Si < Sn && i < n
dp[i]表示以第 i 个元素结尾的子数组的最长递增子序列。
对于一个长度为 N 的序列，最长递增子序列并不一定会以 S~N~ 为结尾，因此 dp[N] 不是序列的最长递增子序列的长度，需要遍历 dp 数组找出最大值才是所要的结果，max{ dp[i] | 1 <= i <= N} 即为所求。
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
int max = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
max = Math.max(max, dp[j] + 1);
}
}
dp[i] = max;
}
int ret = 0;
for (int i = 0; i < n; i++) {
ret = Math.max(ret, dp[i]);
}
return ret;
}
动态规划+二分查找
public int lengthOfLIS (int[] nums) {
int[] dp = new int[nums.length];
int len = 0;
for (int num : nums) {
int i = Arrays.binarySearch(dp,0,len,num);
if (i < 0) i = -(i+1);
dp[i] = num;
if (i == len) len++;
}
return len;
}
646. 最长数对链
难度：中等
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例 :
输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]
注意：
- 给出数对的个数在 [1, 1000] 范围内。
先将给定的数对排序，排序规则是比较数对中第一个数的大小。
然后借用最长递增子序列的思想，用两个循环遍历数组，碰到pairs[j][1] < pairs[i][0]时使用状态转移方程：
dp[i] = Math.max(dp[i], dp[j] + 1)
dp表示以当前元素结尾的最长数对链的长度
public int findLongestChain(int[][] pairs) {
if (pairs.length == 0 || pairs[0].length == 0) {
return 0;
}
int n = pairs.length;
int[] dp = new int[n];
Arrays.fill(dp,1);
Arrays.sort(pairs, Comparator.comparingInt(o -> o[0]));
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int max = 0;
for (int i : dp) {
max = Math.max(max, i);
}
return max;
}
376. 摆动序列
难度：中等
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]
输出: 2
进阶:
你能否用 O(n) 时间复杂度完成此题?
常规动态规划
使用两个数组进行动态规划，up和down
up[i] 表示，目前为止最长的以第 i 个元素结尾的上升摆动序列的长度
down[i] 表示， 目前为止最长的以第 i 个元素结尾的下降摆动序列的长度。
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2)
return nums.length;
int[] up = new int[nums.length];
int[] down = new int[nums.length];
for (int i = 1; i < nums.length; i++) {
for(int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
up[i] = Math.max(up[i],down[j] + 1);
} else if (nums[i] < nums[j]) {
down[i] = Math.max(down[i],up[j] + 1);
}
}
}
return 1 + Math.max(down[nums.length - 1], up[nums.length - 1]);
}
空间优化的动态规划
不用两个数组，用两个变量保存
public int wiggleMaxLength (int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int up = 1, down = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
最长公共子序列
对于两个子序列 S1 和 S2，找出它们最长的公共子序列。
定义一个二维数组 dp用来存储最长公共子序列的长度，其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 S1i 与 S2j 值是否相等，分为两种情况：
当 S1i==S2j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1i 这个值，最长公共子序列长度加 1，即
dp[i][j] = dp[i-1][j-1] + 1。当 S1i != S2j 时，此时最长公共子序列为 S1 的前 i-1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j-1 个字符最长公共子序列，取它们的最大者，即
dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }
综上，最长公共子序列的状态转移方程为：
状态转移方程
$$
\begin{equation}
d p[i][j]=\left{\begin{array}{rlrl}{d p[i-1][j-1]+1} & {} & {S 1_{i}==S 2_{j}} \ {\max (d p[i-1][j], d p[i][j-1])} & {} & {S 1_{i}<>S 2_{j}}\end{array}\right.
\end{equation}
$$
对于长度为 N 的序列 S1 和长度为 M 的序列 S2，dp[N][M] 就是序列 S1 和序列 S2 的最长公共子序列长度。
与最长递增子序列相比，最长公共子序列有以下不同点：
- 针对的是两个序列，求它们的最长公共子序列。
- 在最长递增子序列中，dp[i] 表示以 Si 为结尾的最长递增子序列长度，子序列必须包含 Si ；在最长公共子序列中，
dp[i][j]表示 S1 中前 i 个字符与 S2 中前 j 个字符的最长公共子序列长度，不一定包含 S1i 和 S2j。 - 在求最终解时，最长公共子序列中
dp[N][M]就是最终解，而最长递增子序列中dp[N]不是最终解，因为以 SN 为结尾的最长递增子序列不一定是整个序列最长递增子序列，需要遍历一遍 dp 数组找到最大者。
public int lengthOfLCS(int[] nums1, int[] nums2) {
int n1 = nums1.length, n2 = nums2.length;
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n1][n2];
}
最长公共子串
子串是连续的元素，子序列不一定是连续的元素。
状态转移方程：
$$
d p[i][j]=\left{\begin{array}{rlrl}{d p[i-1][j-1]+1} & {} & {S 1_{i}==S 2_{j}} \ {0} & {} & {S 1_{i}<>S 2_{j}}\end{array}\right.
$$
0-1 背包
基础知识
有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。
定义一个二维数组 dp 存储最大价值，其中dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：
- 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，
dp[i][j] = dp[i-1][j]。 - 第 i 件物品添加到背包中，
dp[i][j] = dp[i-1][j-w] + v。
第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
// W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
public int knapsack(int W, int N, int[] weights, int[] values) {
int[][] dp = new int[N + 1][W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = 1; j <= W; j++) {
if (j >= w) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}
空间优化
在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，
dp[j] = max(dp[j], dp[j-w] + w)
因为 dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[i][j-w]，防止将 dp[i-1][j-w] 覆盖。也就是说要先计算 dp[i][j] 再计算 dp[i][j-w]，在程序实现时需要按倒序来循环求解。
public int knapsack(int W, int N, int[] weights, int[] values) {
int[] dp = new int[W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = W; j >= 1; j--) {
if (j >= w) {
dp[j] = Math.max(dp[j], dp[j - w] + v);
}
}
}
return dp[W];
}
变种
- 完全背包：物品数量为无限个
- 多重背包：物品数量有限制
- 多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制
- 其它：物品之间相互约束或者依赖
416. 分割等和子集
难度：中等
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
实际上就是找到一些元素，使这些元素的和为原数组的和的一半。
这里的背包不是要求总价值最大，而是要求达到目标和的方案数。
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
int target = sum /2;
boolean[] dp = new boolean[target + 1];
dp[0] =true;
for (int num : nums) {
for (int i = target; i >= num ; i--) {
dp[i] = dp[i] || dp[i-num];
}
}
return dp[target];
}
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位整数。
问题转化：
可以将这组数看成两部分，P 和 N，其中 P 使用正号，N 使用负号，有以下推导：
sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)
因此只要找到一个子集，令它们都取正号，并且和等于 (target + sum(nums))/2，就证明存在解。
dp[i]表示用目前为止这些数，能凑出target的组合数
状态转移方程：
dp[i]=dp[i]+dp[i-num]
当前的组合数，分两部分，以算不算上现在这个数为区分。
- 如果不算现在这个数，之前的那么多数有
dp[i]种组合方式达到目标和 - 如果算上现在这个数，之前的那么多数的目标和变成
i-num的组合数，再搭配上现在这个数，就是达到目标和i的组合数
要以倒序遍历数组
public int findTargetSumWays (int[] nums, int S) {
int sum = computeSum(nums);
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int target = (sum + S) / 2;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int num : nums) {
for (int i = target; i >= num; i--) {
dp[i] = dp[i] + dp[i - num];
}
}
return dp[target];
}
private int computeSum (int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}y
填数组过程的表格：
nums/dp[i] |
0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 2 | 1 | 0 | 0 |
| 1 | 1 | 3 | 3 | 1 | 0 |
| 1 | 1 | 4 | 6 | 4 | 1 |
| 1 | 1 | 5 | 10 | 10 | 5 |
474. 一和零
难度：中等
在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意:
- 给定
0和1的数量都不会超过100。 - 给定字符串数组的长度不会超过
600。
示例 1:
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。
示例 2:
输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2
解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
这是一个多维背包问题，dp[i]表示前若干个字符串在 0 数量（体积）、1 数量（重量）不超过 m , n 的时候，能组合出来的最多字符串个数（能达到的最大价值）
public int findMaxForm(String[] strs, int m, int n) {
if (strs == null || strs.length == 0) {
return 0;
}
int[][] dp = new int[m + 1][n + 1];
for (String str : strs) {
int ones = 0, zeros = 0;
for (char c : str.toCharArray()) {
if (c == '0') {
zeros++;
} else {
ones++;
}
}
for (int i = m; i >= zeros; i--) {
for (int j = n; j >= ones; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
322. 零钱兑换
难度：中等
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。
因为硬币可以重复使用，因此这是一个完全背包问题。完全背包只需要将 0-1 背包的逆序遍历 dp 数组改为正序遍历即可。
dp[i]：用目前为止的这几个硬币，凑出 i 这个数，最少需要用几个硬币
public int coinChange (int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
518. 零钱兑换 II
难度：中等
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
注意 :
你可以假设：
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
硬币的个数可以是无限个，这是一个完全背包的问题。
dp[i]：用目前为止的几种硬币，组成i这个目标，可以有多少种组法。
public int change (int amount, int[] coins) {
if (amount == 0 || coins == null || coins.length == 0) {
return 0;
}
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] = dp[i] + dp[i - coin];
}
}
return dp[amount];
}
139. 单词拆分
难度：中等
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
因为可以重复使用字典中的字符串，所以这是一个完全背包问题。
dp[i]表示：用目前为止的几个字符串（物品），能否组合成给定字符串的长度为i的子串（背包）
public boolean wordBreak (String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word : wordDict) {
int length = word.length();
if (length <= i && word.equals(s.substring(i - length, i))) {
dp[i] = dp[i] || dp[i - length];
}
}
}
return dp[n];
}
377. 组合总和 Ⅳ
难度：中等
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
nums = [1, 2, 3]
target = 4
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
进阶：
如果给定的数组中含有负数会怎么样？
问题会产生什么变化？
我们需要在题目中添加什么限制来允许负数的出现？
注意与518. 零钱兑换 II的区别，本题中，顺序不同的序列被视作不同的组合，而在518题中，只要和是一样的，序列的顺序不同也看作是同一组合。
518题中，物品在外循环，背包容量在内循环；而在本题中，目标（背包）在外循环，而物品在内循环。
public int combinationSum4 (int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[target + 1];
dp[0] = 1;
Arrays.sort(nums);
for (int i = 1; i <= target; i++) {
for (int j = 0; j < nums.length && nums[j] <= i; j++) {
dp[i] = dp[i] + dp[i - nums[j]];
}
}
return dp[target];
}
股票交易
参考文章：
字符串编辑
583. 两个字符串的删除操作
难度：中等
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例 1:
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
说明:
- 给定单词的长度不超过500。
- 给定单词中的字符只含有小写字母。
转换为找最长公共子序列问题。
public int minDistance (String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return m + n - 2 * dp[m][n];
}
72. 编辑距离
难度：困难
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2:
输入: word1 = "intention", word2 = "execution"
输出: 5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
所以，
当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
注意，针对第一行，第一列要单独考虑，我们引入 '' 下图所示：
public int minDistance (String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 0; i <= n; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
}
}
return dp[m][n];
}
650. 只有两个键的键盘
难度：中等
最初在一个记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作：
Copy All(复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。Paste(粘贴) : 你可以粘贴你上一次复制的字符。
给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A’。输出能够打印出 n 个 ‘A’ 的最少操作次数。
示例 1:
输入: 3
输出: 3
解释:
最初, 我们只有一个字符 'A'。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 'AA'。
第 3 步, 我们使用 Paste 操作来获得 'AAA'。
说明:
n的取值范围是 [1, 1000] 。
dp[i]表示，通过复制粘贴操作，得到 i 个字符，最少需要几步操作。
如果一个数是素数，那么最少操作就是一开始复制一个，最后一个个粘贴；
如果一个数不是素数，那么最少操作就可以按它的因数分解一下，简化操作。
举个例子，比如12，可以分解为 以下几种情况：
12 = 2*6, 需要操作CPCPPPPP总共8步
12 = 3*4, 需要操作CPPCPPP总共7步
12 = 4*3, 需要操作CPPPCPP总共7步
12 = 6*2, 需要操作CPPPPPCP总共8步
其实可以发现，因子相同的情况下，交换因子相乘的顺序，需要的步骤是一样的。所以我们可以简化一下分解的步骤，只需要找到小于sqrt(n)的因子即可。
假设找到的因子是 j ，那么需要的最小步骤就是 dp[j] + dp[i/j]，其中，dp[j]表示需要多少步生成这个因子，dp[i/j]表示需要多少步基于这个因子得到 i。
public int minSteps(int n) {
int[] dp = new int[n + 1];
int h = (int) Math.sqrt(n);
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = 2; j <= h; j++) {
if (i % j == 0) {
dp[i] = dp[j] + dp[i / j];
break;
}
}
}
return dp[n];
}
