递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算。
斐波那契数列
1. 爬楼梯
70. Climbing Stairs (Easy)
题目描述：有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。
题目描述：有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。
定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp[i] 表示走到第 i 个楼梯的方法数目。
第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。
考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。
回溯法刷的走火入魔，但是用不得，超时了。
class Solution {
private int count=0;
public int climbStairs(int n) {
if(n==1)return 1;
backtrack(n);
return count;
}
private void backtrack(int n){
if(n==0){
++count;
return;
}
else if(n<0){
return;
}
for(int i=1;i<=2;i++){
backtrack(n-i);
}
}
}class Solution {
public int climbStairs(int n) {
if(n<=2){
return n;
}
int p=1,q=2,r=p+q;
for(int i=2;i<n;i++){
p=q;
q=r;
r=p+q;
}
return q;
}
}class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
2. 强盗抢劫
198. House Robber (Easy)
题目描述：抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。
定义 dp 数组用来存储最大的抢劫量，其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。
由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户，所以
class Solution {
public int rob(int[] nums) {
if(nums.length==0||nums==null)return 0;
if (nums.length == 1) {
return nums[0];
}
int[] dp=new int[nums.length];
dp[0]=nums[0];
dp[1]=Math.max(nums[0],nums[1]);
for(int i=2;i<nums.length;i++){
dp[i]=Math.max(dp[i-1],nums[i]+dp[i-2]);
}
return dp[nums.length-1];
}
}3. 强盗在环形街区抢劫
213. House Robber II (Medium)
class Solution {
public int rob(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
int n=nums.length;
if(n==1){
return nums[0];
}
return Math.max(rob(nums,0,n-2),rob(nums,1,n-1));
}
private int rob(int[] nums,int first,int last){
int dp0=0,dp1=0;
for(int i=first;i<=last;i++){
int dp2=Math.max(dp0+nums[i],dp1);
dp0=dp1;
dp1=dp2;
}
return dp1;
}
}矩阵路径
1. 矩阵的最小路径和
64. Minimum Path Sum (Medium)
[[1,3,1],
[1,5,1],
[4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.class Solution {
public int minPathSum(int[][] grid) {
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(i==0&&j==0)continue;
else if(i==0)grid[i][j]=grid[i][j-1]+grid[i][j];
else if(j==0)grid[i][j]=grid[i-1][j]+grid[i][j];
else grid[i][j]=Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
}
}
return grid[grid.length-1][grid[0].length-1];
}
}2. 矩阵的总路径数
62. Unique Paths (Medium)
题目描述：统计从矩阵左上角到右下角的路径总数，每次只能向右或者向下移动。
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp=new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0&&j==0){
dp[i][j]=1;
}
else if(i==0){
dp[i][j]+=dp[i][j-1];
}
else if(j==0){
dp[i][j]+=dp[i-1][j];
}
else dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}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];
}也可以直接用数学公式求解，这是一个组合问题。机器人总共移动的次数 S=m+n-2，向下移动的次数 D=m-1，那么问题可以看成从 S 中取出 D 个位置的组合数量，这个问题的解为 C(S, D)。
public int uniquePaths(int m, int n) {
int S = m + n - 2; // 总共的移动次数
int D = m - 1; // 向下的移动次数
long ret = 1;
for (int i = 1; i <= D; i++) {
ret = ret * (S - D + i) / i;
}
return (int) ret;
}数组区间
1. 数组区间和
303. Range Sum Query - Immutable (Easy)
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3求区间 i ~ j 的和，可以转换为 sum[j + 1] - sum[i]，其中 sum[i] 为 0 ~ i - 1 的和。
用的是缓存的思想
class NumArray {
private int[] sum;
public NumArray(int[] nums) {
sum=new int[nums.length+1];
for(int i=1;i<=nums.length;i++){
sum[i]=sum[i-1]+nums[i-1];
}
}
public int sumRange(int i, int j) {
return sum[j+1]-sum[i];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/2. 数组中等差递增子区间的个数
413. Arithmetic Slices (Medium)
A = [0, 1, 2, 3, 4]
return: 6, for 3 arithmetic slices in A:
[0, 1, 2],
[1, 2, 3],
[0, 1, 2, 3],
[0, 1, 2, 3, 4],
[ 1, 2, 3, 4],
[2, 3, 4]dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。
当 A[i] - A[i-1] == A[i-1] - A[i-2]，那么 [A[i-2], A[i-1], A[i]] 构成一个等差递增子区间。而且在以 A[i-1] 为结尾的递增子区间的后面再加上一个 A[i]，一样可以构成新的递增子区间。
p[2] = 1
[0, 1, 2]
dp[3] = dp[2] + 1 = 2
[0, 1, 2, 3], // [0, 1, 2] 之后加一个 3
[1, 2, 3] // 新的递增子区间
dp[4] = dp[3] + 1 = 3
[0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一个 4
[1, 2, 3, 4], // [1, 2, 3] 之后加一个 4
[2, 3, 4] // 新的递增子区间综上，在 A[i] - A[i-1] == A[i-1] - A[i-2] 时，dp[i] = dp[i-1] + 1。
因为递增子区间不一定以最后一个元素为结尾，可以是任意一个元素结尾，因此需要返回 dp 数组累加的结果。
class Solution {
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 total=0;
for(int cnt: dp){
total+=cnt;
}
return total;
}
}分割整数
1. 分割整数的最大乘积
343. Integer Break (Medim)
class Solution {
public int integerBreak(int n) {
int[] dp=new int[n+1];
for(int i=2;i<=n;i++){
int curMax=0;
for(int j=1;j<i;j++){
curMax=Math.max(curMax,Math.max(j*(i-j),j*dp[i-j]));
}
dp[i]=curMax;
}
return dp[n];
}
}2. 按平方数来分割整数
279. Perfect Squares(Medium)
题目描述：For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
class Solution {
public int numSquares(int n) {
int[] dp=new int[n+1];
for(int i=0;i<=n;i++){
dp[i]=i;
for(int j=1;i-j*j>=0;j++){
dp[i]=Math.min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
}3. 分割整数构成字母字符串
91. Decode Ways (Medium)
题目描述：Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
class Solution {
public int numDecodings(String s) {
int n = s.length();
if (n == 0 || s.charAt(0) == '0') return 0;
int[] dp = new int [n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < n + 1; ++i) {
if (s.charAt(i - 2) == '1' || s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6')
dp[i] += dp[i - 2];
if (s.charAt(i - 1) != '0')
dp[i] += dp[i - 1];
}
return dp[n];
}
}最长递增子序列
1. 最长递增子序列
300. Longest Increasing Subsequence (Medium)
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length==0){
return 0;
}
int[] dp=new int[nums.length];
dp[0]=1;
int maxans=1;
for(int i=1;i<nums.length;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
maxans=Math.max(maxans,dp[i]);
}
return maxans;
}
}2. 一组整数对能够构成的最长链
646. Maximum Length of Pair Chain (Medium)
Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]题目描述：对于 (a, b) 和 (c, d) ，如果 b < c，则它们可以构成一条链。
class Solution {
public int findLongestChain(int[][] pairs) {
if(pairs.length==0){
return 0;
}
int[] dp=new int[pairs.length];
Arrays.fill(dp,1);
int maxnum=0;
Arrays.sort(pairs,(a,b)->(a[0]-b[0]));
for(int i=1;i<pairs.length;i++){
for(int j=0;j<i;j++){
if(pairs[j][1]<pairs[i][0]){
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
maxnum=Math.max(maxnum,dp[i]);
}
return maxnum;
}
}3. 最长摆动子序列
376. Wiggle Subsequence (Medium)
class Solution {
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);
}
}最长公共子序列
1. 最长公共子序列
1143. Longest Common Subsequence
public int longestCommonSubsequence(String text1, String text2) {
int n1 = text1.length(), n2 = text2.length();
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (text1.charAt(i - 1) == text2.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 dp[n1][n2];
}0-1 背包
// 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];
}
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];
}1. 划分数组为和相等的两部分
416. Partition Equal Subset Sum (Medium)
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].class Solution {
public boolean canPartition(int[] nums) {
int sum=0;
for(int i: nums){
sum+=i;
}
if(sum %2 !=0 ){
return false;
}
int W=sum/2;
boolean[] dp=new boolean[W+1];
dp[0]=true;
for(int num:nums){
for(int i=W;i>=num;i--){
dp[i]=dp[i]||dp[i-num];
}
}
return dp[W];
}
}2. 改变一组数的正负号使得它们的和为一给定数
494. Target Sum (Medium)
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-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
There are 5 ways to assign symbols to make the sum of nums be target 3.该问题可以转换为 Subset Sum 问题，从而使用 0-1 背包的方法来求解。
可以将这组数看成两部分，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，就证明存在解。
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for(int num: nums){
sum+=num;
}
if(sum < S || (sum + S) % 2 == 1){
return 0;
}
int W = (sum + S) / 2;
int[] dp=new int[W+1];
dp[0]=1;
for(int num:nums){
for(int i=W;i>=num;i--){
dp[i]=dp[i]+dp[i-num];
}
}
return dp[W];
}
}3. 01 字符构成最多的字符串
474. Ones and Zeroes (Medium)
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: There are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0"这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和 1 的数量。
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 s : strs) { // 每个字符串只能用一次
int ones = 0, zeros = 0;
for (char c : s.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];
}4. 找零钱的最少硬币数
322. Coin Change (Medium)
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.题目描述：给一些面额的硬币，要求用这些硬币来组成给定面额的钱数，并且使得硬币数量最少。硬币可以重复使用。
- 物品：硬币
- 物品大小：面额
- 物品价值：数量
因为硬币可以重复使用，因此这是一个完全背包问题。完全背包只需要将 0-1 背包的逆序遍历 dp 数组改为正序遍历即可。
class Solution {
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+1;i++){
for(int j=0;j<coins.length;j++){
if(i-coins[j]>=0){
dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
}
}
}
return dp[amount]==amount+1?-1:dp[amount];
}
}5. 找零钱的硬币数组合
518. Coin Change 2 (Medium)
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1完全背包问题，使用 dp 记录可达成目标的组合数目。
class Solution {
public int change(int amount, int[] coins) {
if(coins==null){
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-coin];
}
}
return dp[amount];
}
}6. 字符串按单词列表分割
139. Word Break (Medium)
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".dict 中的单词没有使用次数的限制，因此这是一个完全背包问题。
该问题涉及到字典中单词的使用顺序，也就是说物品必须按一定顺序放入背包中，例如下面的 dict 就不够组成字符串 "leetcode"：
["lee", "tc", "cod"]求解顺序的完全背包问题时，对物品的迭代应该放在最里层，对背包的迭代放在外层，只有这样才能让物品按一定顺序放入背包中。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n=s.length();
boolean[] dp=new boolean[n+1];
dp[0]=true;
for(String word:wordDict){
for(int i=1;i<=n;i++){
int len=word.length();
if(len<=i && word.equals(s.substring(i-len,i))){
dp[i]=dp[i]||dp[i-len];
}
}
}
return dp[n];
}
}7. 组合总和
377. Combination Sum IV (Medium)
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.涉及顺序的完全背包。
class Solution {
public int combinationSum4(int[] nums, int target) {
if(target==0|nums.length==0||nums==null){
return 0;
}
int[] dp = new int[target+1];
dp[0]=1;
for(int i=0;i<=target;i++){
for(int num:nums){
if(i>=num){
dp[i]=dp[i]+dp[i-num];
}
}
}
return dp[target];
}
}股票交易
推荐看这个模板
这个问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：
这个解释应该很清楚了，如果 buy，就要从利润中减去 prices[i]，如果 sell，就要给利润增加 prices[i]。今天的最大利润就是这两种可能选择中较大的那个。而且注意 k 的限制，我们在选择 buy 的时候，把 k 减小了 1，很好理解吧，当然你也可以在 sell 的时候减 1，一样的。
现在，我们已经完成了动态规划中最困难的一步：状态转移方程。如果之前的内容你都可以理解，那么你已经可以秒杀所有问题了，只要套这个框架就行了。不过还差最后一点点，就是定义 base case，即最简单的情况。
第一题，k = 1 121. 买卖股票的最佳时机
直接套状态转移方程，根据 base case，可以做一些化简：
class Solution {
public int maxProfit(int[] prices) {
int n=prices.length;
if(n==0){
return 0;
}
int dp_i_0=0;//没有股票
int dp_i_1=-prices[0];//有股票
for(int i=0;i<n;i++){
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
//要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
//要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。
dp_i_1=Math.max(dp_i_1,-prices[i]);
//要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
//要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。
}
return dp_i_0;
}
}第二题，k = +infinity 122. 买卖股票的最佳时机 II
class Solution {
public int maxProfit(int[] prices) {
int n=prices.length;
int dp_i_0=0, dp_i_1=-1;
for(int i=0;i<n;i++){
int temp=dp_i_0;
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1=Math.max(dp_i_1,temp-prices[i]);
}
return dp_i_0;
}
}第三题，k = +infinity with cooldown 309. 最佳买卖股票时机含冷冻期
class Solution {
public int maxProfit(int[] prices) {
int n=prices.length;
int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
int dp_pre_0=0;//用来表示dp[i-2][0]
for(int i=0;i<n;i++){
int temp=dp_i_0;
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1=Math.max(dp_i_1,dp_pre_0-prices[i]);
dp_pre_0=temp;
}
return dp_i_0;
}
}第四题，k = +infinity with fee 714. 买卖股票的最佳时机含手续费
class Solution {
public int maxProfit(int[] prices, int fee) {
int n=prices.length;
int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
for(int i=0;i < n;i++){
int temp=dp_i_0;
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1=Math.max(dp_i_1,temp-prices[i]-fee);
}
return dp_i_0;
}
}第五题，k = 2 123. 买卖股票的最佳时机 III
public class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
// 第 2 维的 0 没有意义，1 表示交易进行了 1 次，2 表示交易进行了 2 次
// 为了使得第 2 维的数值 1 和 2 有意义，这里将第 2 维的长度设置为 3
int[][][] dp = new int[len][3][2];
// 理解如下初始化
// 第 3 维规定了必须持股，因此是 -prices[0]
dp[0][1][1] = -prices[0];
// 还没发生的交易，持股的时候应该初始化为负无穷
dp[0][2][1] = Integer.MIN_VALUE;
for (int i = 1; i < len; i++) {
// 转移顺序先持股，再卖出
dp[i][1][1] = Math.max(dp[i - 1][1][1], -prices[i]) ;
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i]);
dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i]);
dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i]);
}
return Math.max(dp[len - 1][1][0], dp[len - 1][2][0]);
}
}第六题，k = any integer188. 买卖股票的最佳时机 IV
一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。
class Solution {
public int maxProfit(int k, int[] prices) {
if(prices==null || prices.length==0) return 0;
int n=prices.length;
if(k>=n/2) return geedy(prices);
int[][][] dp=new int[n+1][k+1][2];
//初始化，把持股的部分都设置为一个较大的负值,和之前的初始化类似
for(int i=0;i<=n;i++){
for(int j=0;j<=k;j++){
dp[i][j][1]=-9999;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]);
dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]);
}
}
return dp[n][k][0];
}
int geedy(int[] prices){
int res=0;
for(int i=1;i<prices.length;i++){
if(prices[i-1]<prices[i]) {
res+=prices[i]-prices[i-1];
}
}
return res;
}
}1. 需要冷却期的股票交易
309. Best Time to Buy and Sell Stock with Cooldown(Medium)
class Solution {
public int maxProfit(int[] prices) {
// sell[i]表示截至第i天，最后一个操作是卖时的最大收益；
// buy[i]表示截至第i天，最后一个操作是买时的最大收益；
// cool[i]表示截至第i天，最后一个操作是冷冻期时的最大收益；
// 递推公式：
// sell[i] = max(buy[i-1]+prices[i], sell[i-1]) (第一项表示第i天卖出，第二项表示第i天冷冻)
// buy[i] = max(cool[i-1]-prices[i], buy[i-1]) （第一项表示第i天买进，第二项表示第i天冷冻）
// cool[i] = max(sell[i-1], buy[i-1], cool[i-1])
int N=prices.length;
if(N==0){
return 0;
}
int[] sell=new int[N];
int[] buy=new int[N];
int[] cool =new int[N];
buy[0]=-prices[0];
for(int i=1;i<N;i++){
sell[i]=Math.max(buy[i-1]+prices[i],sell[i-1]);
buy[i]=Math.max(cool[i-1]-prices[i],buy[i-1]);
cool[i]=Math.max(Math.max(sell[i-1],buy[i-1]),cool[i-1]);
}
return sell[N-1];
}
}题目描述：交易之后需要有一天的冷却时间。
字符串编辑
1. 删除两个字符串的字符使它们相等
583. Delete Operation for Two Strings (Medium)
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".class Solution {
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][j-1],dp[i-1][j]);
}
}
}
return m+n-2*dp[m][n];
}
}2. 编辑距离
72. Edit Distance (Hard)
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')题目描述：修改一个字符串成为另一个字符串，使得修改次数最少。一次修改操作包括：插入一个字符、删除一个字符、替换一个字符。
class Solution {
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++){
dp[i][0]=i;
}
for(int j=1;j<=n;j++){
dp[0][j]=j;
}
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]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
}
}
return dp[m][n];
}
}3. 复制粘贴字符
650. 2 Keys Keyboard (Medium)
题目描述：最开始只有一个字符 A，问需要多少次操作能够得到 n 个字符 A，每次操作可以复制当前所有的字符，或者粘贴。
class Solution {
public int minSteps(int n) {
// 其实可以发现，因子相同的情况下，交换因子相乘的顺序，需要的步骤是一样的。所以我们可以简化一下分解的步骤，只需要找到小于sqrt(n)的因子即可。
// 假设找到的因子是 j ，那么需要的最小步骤就是 dp[j] + dp[i/j]，其中，dp[j]表示需要多少步生成这个因子，dp[i/j]表示需要多少步基于这个因子得到 i
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];
}
}难度中等9
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
class Solution {
public int numTrees(int n) {
int[] dp=new int[n+1];
dp[0]=1;
dp[1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i]+=dp[j-1]*dp[i-j];
}
}
return dp[n];
}
}