关于动态规划内容很多，这里只列举一些我觉都有意思的题目。
二维简单动态规划
最小路径和
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] 此时不用任何操作。如果不相等，就可以进行三种操作。
- 插入s1[i]， 但需要s1前i个字符和s2前j-1个字符相等。就是dp[i][j-1]。最后加上插入代价 + a
- 删除s1[i]， 但需要s1前i-1个字符和s2前j个字符相等。就是dp[i-1][j]。最后加上删除代价 + b
- 替换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;
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个字符。然后判断
- 如果s1[i-1] == s3[i+j-1]，说明是s1提供了最后一个字符，那么此时我就保证s1的前i-1个字符和s2的前j个字符可以交错组成s3的前i+j-1个字符。即dp[i-1][j];
- 如果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;
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;
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;
}
|
wechat