关于动态规划内容很多，这里只列举一些我觉都有意思的题目。

二维简单动态规划

最小路径和

leetcode 64

思路：状态转移方程：f[i][j] = Math.min(f[i-1][j],f[i][j-1]) + grid[i][j] 因为一个位置只能从上或者左转移过来，所以状态转移方程就是这个样子的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minPathSum(int[][] grid) {
    int n = grid.length;
    int m = grid[0].length;
    int[] dp = new int[m];
    dp[0] = grid[0][0];
    for(int i=1;i<m;i++){
        dp[i] = grid[0][i]+dp[i-1];
    }
    for(int i = 1;i<n;i++){
        dp[0]+=grid[i][0];
        for(int j = 1;j<m;j++){
           dp[j] = Math.min(dp[j-1],dp[j]) + grid[i][j];
        }
    } 
    return dp[m-1];
}

最长公共子序列

leetcode 1143

思路：状态转移方程：f[i][j] = if(s1[i]==s2[j]) f[i-1][j-1]+1 else max(f[i-1][j],f[i][j-1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int longestCommonSubsequence(String text1, String text2) {
    char[] s1 = text1.toCharArray();
    char[] s2 = text2.toCharArray();
    int n =s1.length;
    int m = s2.length;
    int[][] dp = new int[n+1][m+1];
    for(int i=1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(s1[i-1] == s2[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[n][m];
}

最长回文子序列

leetcode 516

思路：第一种思路，把原字符串翻转，然后求最长子序列。

第二种思路，二维dp,记录从l到r的回文子序列的长度。 初始化dp[i][i] = 1;,dp[i][i+1] = s[i] == s[i+1] ? 2 : 1; 每个格子依赖于左下，下，左边的格子。于是dp的顺序就是从下到上，从左到右。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    char[] c = s.toCharArray();
    int[][] dp = new int[n][n];
    for(int l = n-1;l>=0;l--){
        dp[l][l] = 1;
        if(l+1<n){
            dp[l][l+1] = c[l] == c[l+1] ? 2 : 1;
        }
        for(int r = l+2;r<n;r++){
            if(c[r] == c[l]){
                dp[l][r] = dp[l+1][r-1]+2;
            }else {
                dp[l][r] = Math.max(dp[l+1][r],dp[l][r-1]);
            }
        }
    }
    return dp[0][n-1];
}

不同的子序列

leetcode 115

思路：dp[i][j] 表示s1的前i个字符，s2的前j个字符，有多少个不同的子序列。 那么当s1[i]==s2[j] 时，dp[i][j] = dp[i-1][j-1]+dp[i-1][j] 否则dp[i][j] = dp[i-1][j]
然后初始化dp[i][0] = 1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++)
        dp[i][0] = 1;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j <= Math.min(i,n-1); j++) {
            if (s.charAt(i) == t.charAt(j)) {
                dp[i+1][j+1] = dp[i][j] + dp[i][j+1];
            } else {
                dp[i+1][j+1] = dp[i][j+1];
            }
        }
    }
    return dp[m][n];
}

//压缩
public int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    int[] dp = new int[n + 1];
    for (int i = 1; i <= m; i++) {
        dp[0] = 1;
        for (int j = Math.min(i,n); j >=1; j--) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[j] = dp[j-1] + dp[j];
            }
        }
    }
    return dp[n];
}

编辑距离

leetcode 72 在此基础上新增了每种操作的代价。

思路：dp[i][j]含义为需要多少代价才能使得s1前i个字符和s2前j个字符相等。当s1[i] == s2[j]时，dp[i][j] = dp[i-1][j-1] 此时不用任何操作。如果不相等，就可以进行三种操作。

  1. 插入s1[i]， 但需要s1前i个字符和s2前j-1个字符相等。就是dp[i][j-1]。最后加上插入代价 + a
  2. 删除s1[i]， 但需要s1前i-1个字符和s2前j个字符相等。就是dp[i-1][j]。最后加上删除代价 + b
  3. 替换s1[i]， 但需要s1前i-1个字符和s2前j-1个字符相等。就是dp[i-1][j-1]。最后加上替换代价 + c

初始化时dp[0][j] = j a（因为从空字符串到s2只能插入）; dp[i][0] = i b（从s1到空字符串只能删除）;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public static int editDistance2(String str1, String str2, int a, int b, int c) {
	char[] s1 = str1.toCharArray();
	char[] s2 = str2.toCharArray();
	int n = s1.length;
	int m = s2.length;
	// dp[i][j] :
	// s1[前缀长度为i]想变成s2[前缀长度为j]，至少付出多少代价
	int[][] dp = new int[n + 1][m + 1];
	for (int i = 1; i <= n; i++) {
		dp[i][0] = i * b;
	}
	for (int j = 1; j <= m; j++) {
		dp[0][j] = j * a;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (s1[i - 1] == s2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1];
			} else {
				dp[i][j] = Math.min(Math.min(dp[i - 1][j] + b, dp[i][j - 1] + a), dp[i - 1][j - 1] + c);
			}
		}
	}
	return dp[n][m];
}

  //空间压缩
   private int fff(char[] s1, char[] s2, int a, int b, int c) {
       int n = s1.length;
       int m = s2.length;
       int[] dp = new int[m+1];
       for(int i=1;i<=m;i++){
           dp[i] = i*a;
       }
       for(int i=1;i<=n;i++){
           int leftup = dp[0] ,backup;
           dp[0] = i*b;
           for(int j=1;j<=m;j++){
               backup = dp[j];
               if(s1[i-1] == s2[j-1]){
                   dp[j] = leftup;
               }else {
                   dp[j] = Math.min(Math.min(dp[j-1]+a,dp[j]+b),leftup+c);
               }
               leftup = backup;
           }
       }
       return dp[m];
   }

交错字符串

leetcode 97

思路： dp[i][j]表示s1的前i个字符和s2的前j个字符是否可以交错组成s3的前i+j个字符。然后判断

  1. 如果s1[i-1] == s3[i+j-1]，说明是s1提供了最后一个字符，那么此时我就保证s1的前i-1个字符和s2的前j个字符可以交错组成s3的前i+j-1个字符。即dp[i-1][j];
  2. 如果s2[j-1] == s3[i+j-1]，说明是s2提供了最后一个字符，那么此时我就保证s1的前i个字符和s2的前j-1个字符可以交错组成s3的前i+j-1个字符。即dp[i][j-1];

初始化： dp[i][0] 表示 s2不参与拼接，就是纯靠s1去拼接s3的前i个字符。 dp[0][j] 表示 s1不参与拼接，就是纯靠s2去拼接s3的前j个字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static boolean isInterleave1(String str1, String str2, String str3) {
	if (str1.length() + str2.length() != str3.length()) {
		return false;
	}
	char[] s1 = str1.toCharArray();
	char[] s2 = str2.toCharArray();
	char[] s3 = str3.toCharArray();
	int n = s1.length;
	int m = s2.length;
	// dp[i][j]:
	// s1[前缀长度为i]和s2[前缀长度为j]，能否交错组成出s3[前缀长度为i+j]
	boolean[][] dp = new boolean[n + 1][m + 1];
	dp[0][0] = true;
	for (int i = 1; i <= n; i++) {
		if (s1[i - 1] != s3[i - 1]) {
			break;
		}
		dp[i][0] = true;
	}
	for (int j = 1; j <= m; j++) {
		if (s2[j - 1] != s3[j - 1]) {
			break;
		}
		dp[0][j] = true;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]);
		}
	}
	return dp[n][m];
}

子数组和相关问题

子数组最大和

leetcode 53

思路：dp[i]表示以i为结尾的子数组的和最大是多少。那么dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int maxSubArray1(int[] nums) {
	int n = nums.length;
	// dp[i] : 子数组必须以i位置的数做结尾，往左能延伸出来的最大累加和
	int[] dp = new int[n];
	dp[0] = nums[0];
	int ans = nums[0];
	for (int i = 1; i < n; i++) {
		dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
		ans = Math.max(ans, dp[i]);
	}
	return ans;
}

// 空间压缩
public static int maxSubArray2(int[] nums) {
	int n = nums.length;
	int ans = nums[0];
	for (int i = 1, pre = nums[0]; i < n; i++) {
		pre = Math.max(nums[i], pre + nums[i]);
		ans = Math.max(ans, pre);
	}
	return ans;
}

循环数组中子数组的最大和

leetcode 918

思路：求子数组最大和跟最小和即可。用sum - minSum 就是分开的子数组的最大和。 但需要特判一下是不是全是负数的情况.

1
2
3
4
5
6
7
8
9
10
11
public int maxSubarraySumCircular(int[] nums) {
    int maxSum = nums[0] ,minSum = nums[0],preMax=nums[0],preMin=nums[0],sum=nums[0];
    for(int i =1;i< nums.length;i++){
        sum+=nums[i];
        preMax = Math.max(preMax+nums[i],nums[i]);
        maxSum = Math.max(maxSum,preMax);
        preMin = Math.min(preMin+nums[i],nums[i]);
        minSum = Math.min(minSum,preMin);
    }
    return sum == minSum ? maxSum : (Math.max(maxSum, sum - minSum));
}

打家劫舍2

leetcode 213

思路：分开讨论即可，要么不偷第一家，在2-n之间偷，要么偷第一家，在1-n-1之间偷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int rob2(int[] nums) {
    int n =nums.length;
    if(n==1){
        return nums[0];
    }
    //分开讨论
    int[] dp1 = new int[n+1];
    int[] dp2 = new int[n+1];

    //不拿第一家
    dp1[0] = 0;
    dp1[1] = 0;
    for(int i =2;i<=n;i++){
        dp1[2] = Math.max(dp1[i-1],dp1[i-2]+nums[i-1]);
    }
    //不拿最后一家
    dp2[0] = 0;
    dp2[1] = nums[0];
    for(int i = 2;i<n;i++){
        dp2[i] = Math.max(dp2[i-1],dp2[i-2]+nums[i-1]);
    }
    return Math.max(dp1[n],dp2[n-1]);
}

打家劫舍4

leetcode 2560

思路：二分+dp。 转化为给定能力，小偷最多偷多少家即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public int minCapability(int[] nums, int k) {
    int n = nums.length;
    int max = 0;
    for(int i=0;i<n;i++){
        max = Math.max(nums[i],max);
    }
    int r =max;
    int l=0;
    int ans = r;
    while(l<=r){
        int mid = l + ((r-l)>>1);
        if(f(nums,mid,k)){
            ans = mid;
            r = mid -1;
        }else {
            l = mid + 1;
        }
    }
    return ans;
}

public boolean f(int[] nums,int cap,int k){
    int n = nums.length;
    int[] dp = new int[n+1];
    dp[0] = 0;
    dp[1] = cap >= nums[0] ? 1 : 0;
    for(int i=2;i<=n;i++){
        if(nums[i-1] > cap){
            dp[i] = dp[i-1];
        }else {
            dp[i] = Math.max(dp[i-1],dp[i-2]+1);
        }
        if(dp[i] >= k){
            return true;
        }
    }
    return dp[n] >= k;
}

乘积最大子数组

leetcode 152

思路：dp1[i] 表示以i为结尾的子数组乘积最大是多少。dp2[i] 表示以i为结尾的子数组乘积最小是多少。 每次正在一个位置比较最小值乘以自己，最大值乘以自己，跟自己的大小即可。并且更新dp1[i]，dp2[i]。 代码直接给出空间压缩版本.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxProduct(int[] nums) {
    int n = nums.length;
    int min = nums[0];
    int max = nums[0];
    int ans = nums[0];
    int temp;
    for(int i =1;i<n;i++){
        temp = max;
        temp = Math.max(Math.max(max*nums[i],min*nums[i]),nums[i]);
        min = Math.min(Math.min(min*nums[i],max*nums[i]),nums[i]);
        max = temp;
        ans = Math.max(max,ans);
    }
    return ans;
}

被7整除的最大子序列和

思路：dp[i][j] 表示以第i个数为结尾，模数为j的子序列和最大是多少。那么dp[i][j] = dp[i-1][j] 或者 dp[i-1][(j+7-nums[i-1]%7)%7] + nums[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int maxSum2(int[] nums) {
		int n = nums.length;
		// dp[i][j] : nums[0...i-1]
		// nums前i个数形成的子序列一定要做到，子序列累加和%7 == j
		// 这样的子序列最大累加和是多少
		// 注意 : dp[i][j] == -1代表不存在这样的子序列
		int[][] dp = new int[n + 1][7];
		dp[0][0] = 0;
		for (int j = 1; j < 7; j++) {
			dp[0][j] = -1;
		}
		for (int i = 1, x, cur, need; i <= n; i++) {
			x = nums[i - 1];
			cur = nums[i - 1] % 7;
			for (int j = 0; j < 7; j++) {
				dp[i][j] = dp[i - 1][j];
				// 这里求need是核心
				need = cur <= j ? (j - cur) : (j - cur + 7);
				// 或者如下这种写法也对
				// need = (7 + j - cur) % 7;
				if (dp[i - 1][need] != -1) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][need] + x);
				}
			}
		}
		return dp[n][0];
	}

可以翻转1次的情况下子数组最大累加和

给定一个数组nums，

现在允许你随意选择数组连续一段进行翻转，也就是子数组逆序的调整

比如翻转[1,2,3,4,5,6]的[2~4]范围，得到的是[1,2,5,4,3,6]

返回必须随意翻转1次之后，子数组的最大累加和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static int maxSumReverse2(int[] nums) {
		int n = nums.length;
		// start[i] : 所有必须以i开头的子数组中，最大累加和是多少
		int[] start = new int[n];
		start[n - 1] = nums[n - 1];
		for (int i = n - 2; i >= 0; i--) {
			// nums[i]
			// nums[i] + start[i+1]
			start[i] = Math.max(nums[i], nums[i] + start[i + 1]);
		}
		int ans = start[0];
		// end : 子数组必须以i-1结尾，其中的最大累加和
		int end = nums[0];
		// maxEnd :
		// 0~i-1范围上，
		// 子数组必须以0结尾，其中的最大累加和
		// 子数组必须以1结尾，其中的最大累加和
		// ...
		// 子数组必须以i-1结尾，其中的最大累加和
		// 所有情况中，最大的那个累加和就是maxEnd
		int maxEnd = nums[0];
		for (int i = 1; i < n; i++) {
			// maxend   i....
			// 枚举划分点 i...
			ans = Math.max(ans, maxEnd + start[i]);
			// 子数组必须以i结尾，其中的最大累加和
			end = Math.max(nums[i], end + nums[i]);
			maxEnd = Math.max(maxEnd, end);
		}
		ans = Math.max(ans, maxEnd);
		return ans;
	}

最长递增子序列相关题目

最长递增子序列

leetcode 300

思路：最基础的复杂度O(n^2)，优化版本

维护一个ends[]数组，表示ends[i]表示长度为i+1的递增子序列的最小末尾元素。那么以后我要新增一个元素，那么我需要二分找到大于等于这个元素的最左位置，然后更新这个位置的元素为这个元素。如果没找到，那么就插入到数组末尾。并且len++。最后返回len即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 时间复杂度O(n * logn)
public static int lengthOfLIS(int[] nums) {
	int n = nums.length;
	int[] ends = new int[n];
	// len表示ends数组目前的有效区长度
	// ends[0...len-1]是有效区，有效区内的数字一定严格升序
	int len = 0;
	for (int i = 0, find; i < n; i++) {
		find = bs1(ends, len, nums[i]);
		if (find == -1) {
			ends[len++] = nums[i];
		} else {
			ends[find] = nums[i];
		}
	}
	return len;
}

// "最长递增子序列"使用如下二分搜索 :
// ends[0...len-1]是严格升序的，找到>=num的最左位置
// 如果不存在返回-1
public static int bs1(int[] ends, int len, int num) {
	int l = 0, r = len - 1, m, ans = -1;
	while (l <= r) {
		m = (l + r) / 2;
		if (ends[m] >= num) {
			ans = m;
			r = m - 1;
		} else {
			l = m + 1;
		}
	}
	return ans;
}

俄罗斯套娃信封

leetcode 354

思路：先将宽高进行排序，按宽度升序，高度降序。然后对于高度求最长递增子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes,(a,b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
    int n = envelopes.length;
    int[] ends = new int[n];
    int len = 0;
    for(int i=0;i<n;i++){
        int find = bs1(ends,len,envelopes[i][1]);
        if(find == -1){
            ends[len++] = envelopes[i][1];
        }else {
            ends[find] = envelopes[i][1];
        }
    }
    return len;
}

private int bs1(int[] ends, int len, int target) {
    int l=0,r=len-1,ans=-1;
    while(l<=r){
        int mid = l + ((r-l)>>1);
        if(ends[mid] >= target){
            ans = mid;
            r = mid-1;
        }else {
            l = mid+1;
        }
    }
    return ans;
}

最长对数链

leetcode 646

思路：每个数对按第一个数降序排列。然后求最长递增子序列。但是注意，这里在二分查找的时候，查找跟放入的不是一个数。按开始位置进行查找，但是放入自己的结束位置，所以不能直接放入，应该判断跟原位置的大小（因为这里只能知道开始的值是小于等于找到的位置的，结束值跟这个位置的大小关系不确定）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private int bs1(int[] ends, int len, int target) {
    int l=0,r=len-1,ans=-1;
    while(l<=r){
        int mid = l + ((r-l)>>1);
        if(ends[mid] >= target){
            ans = mid;
            r = mid-1;
        }else {
            l = mid+1;
        }
    }
    return ans;
}

public int findLongestChain(int[][] pairs) {
    Arrays.sort(pairs,(a,b)-> a[0] - b[0]);
    int n =pairs.length;
    int[] ends = new int[n];
    int len =0;
    for(int i=0;i<n;i++){
        //根据开始值进行二分查找 找个大于等于自己的最左位置
        int find = bs1(ends,len,pairs[i][0]);
        if(find == -1){
            ends[len++] = pairs[i][1];
        }else {
            // 这里不能直接放入 而是应该判断跟原位置的大小关系
            ends[find] = Math.min(pairs[i][1],ends[find]);
        }
    }
    return len;
}