动态规划
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 uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
if (obstacleGrid[i][0] == 1) break;
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
if (obstacleGrid[0][i] == 1) break;
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
continue;
}
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
|
递推公式: dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
1
2
3
4
5
6
7
8
9
10
| public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j <= i - j; j++) {
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
|
1
2
3
4
5
6
7
8
9
10
11
| 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];
}
|
0-1背包理论基础(一)
题目描述: 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。
即： 重量数组weight, 价值数组value。
dp数组dp[i][j] i表征前i个物品，j表征背包的容量。
数组初始化: dp[i][0] = 0;因为背包容量为0. dp[0][j] = j >= weight[0] ? value[0] : 0;
递推公式: dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i]);
递推方向: 先遍历背包还是先遍历物品都行，但一般都是先遍历物品，因为更好理解:
1
2
3
4
5
6
| for (int i = 0; i < value.length; i++) {
for (int j = 0; j <= badweight; j++) {
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
|
0-1背包理论基础(二)
dp[i][j]降维为dp[j], 递推公式更新为dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); 初始化为dp[0] = 0
递推公式如下:
1
2
3
4
5
| for (int i = 0; i < value.length; i++) {
for (int j = badweight; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
|
先凑一半 求最大值，然后再处理:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int i : stones) {
sum += i;
}
int target = sum / 2;
int[] dp = new int[target + 1];
dp[0] = 0;
for (int i = 0; i < stones.length; i++) {
for (int j = target; j >= stones[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
|
动态规划组合问题: 初始化 dp[0] = 1 递推公式为dp[j] += dp[j - nums[i]];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int i: nums) {
sum += i;
}
target = sum + target;
if (target % 2 != 0 || target < 0) return 0;
target /= 2;
if (target > sum) return 0;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i < nums.length; i ++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
|
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 findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
dp[0][0] = 0;
}
for (int i = 0; i < strs.length; i++) {
int[] weights = weight(strs[i]);
for (int j = m; j >= weights[0]; j--) {
for (int k = n; k >= weights[1]; k--) {
dp[j][k] = Math.max(dp[j - weights[0]][k - weights[1]] + 1, dp[j][k]);
}
}
}
return dp[m][n];
}
private int[] weight(String str) {
int[] weight = new int[2];
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '0') weight[0]++;
else weight[1]++;
}
return weight;
}
|
完全背包理论基础
完全背包和零一背包的主要区别在于完全背包问题允许物品重复取用和放置，所以完全背包问题关于背包大小的遍历顺序是正序而非倒序，即:
1
2
3
4
| for (int i = 0; i < value.length; i++) {
for (int j = weight[i]; j <= bagsize; j ++) {}
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
|
因为双正序，所以实际上遍历顺序也就没有差别了:
1
2
3
4
5
| for (int j = 0; j <= bagsize; j++) {
for (int i = 0; i < value.length; i++) {}
if (j < weight[i]) continue;
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
|
因为是排列问题，所以背包优先:
1
2
3
4
5
6
7
8
9
10
| public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int j = 0; j <= target; j++) {
for (int i = 0;i < nums.length; i++) {
if (j >= nums[i]) dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> hashSet = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1;i <= s.length(); i++) {
for (int j = 0; j < i && !dp[i]; j++) {
if (hashSet.contains(s.substring(j, i)) && dp[j]) {
dp[i] = true;
}
}
}
return dp[s.length()];
}
|
多重背包理论基础
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
实际上，多重背包问题可以看作是01背包问题，因为物品数目有限而且可以列举。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
int rob1 = robRange(nums, 0, nums.length - 2);
int rob2 = robRange(nums, 1, nums.length - 1);
return Math.max(rob1, rob2);
}
private int robRange(int[] nums,int start,int end) {
int[] dp = new int[nums.length];
dp[start] = nums[start];
if (start == end) return dp[start];
dp[start + 1] = Math.max(dp[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[end];
}
|
所谓树形dp，其递归的过程主要集中在递归的返回值。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int rob(TreeNode root) {
int [] dp = robTree(root);
return Math.max(dp[0], dp[1]);
}
private int[] robTree(TreeNode root) {
int[] dp = new int[2];
if (root == null) return dp;
int[] left = robTree(root.left);
int[] right = robTree(root.right);
dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
dp[1] = root.val + left[0] + right[0];
return dp;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int maxProfit(int k, int[] prices) {
int[][] dp = new int[prices.length][2 * k];
for (int i = 1; i <= k; i++) {
dp[0][2 * i - 2] = -prices[0];
dp[0][2 * i - 1] = 0;
}
for (int i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
for (int j = 2; j <= k; j++) {
dp[i][2 * j - 2] = Math.max(dp[i - 1][2 * j - 2], dp[i - 1][2 * j - 3] - prices[i]);
dp[i][2 * j - 1] = Math.max(dp[i - 1][2 * j -1], dp[i - 1][2* j - 2] + prices[i]);
}
}
return dp[prices.length - 1][2 * k - 1];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
}
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
}
int max = dp[0];
for (int i: dp){
if (i > max) max = i;
}
return max;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public int findLength(int[] nums1, int[] nums2) {
int max = 0;
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
for (int i = 0; i <= nums1.length; i++) {
dp[i][0] = 0;
}
for (int i = 0; i <= nums2.length; i++) {
dp[0][i] = 0;
}
for (int i = 1; i <= nums1.length; i++) {
for (int j = 1; j <= nums2.length; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > max) max = dp[i][j];
}
}
}
return max;
}
|
等同于求最长公共子序列:
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int maxUncrossedLines(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
for (int i = 1; i <= nums1.length; i++){
for (int j = 1; j <= nums2.length; 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[nums1.length][nums2.length];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int numDistinct(String s, String t) {
int[][] dp = new int[s.length() + 1][t.length() + 1];
for (int i = 0; i <= s.length(); i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= t.length(); j++){
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[s.length()][t.length()];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 0; i <= word1.length(); i++) {
dp[i][0] = i;
}
for (int i = 0; i <= word2.length(); i++) {
dp[0][i] = i;
}
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1 ;
}
}
}
return dp[word1.length()][word2.length()];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int countSubstrings(String s) {
int[] dp = new int[s.length() + 1];
for (int i = 1; i <= s.length(); i++) {
dp[i] = dp[i - 1];
for (int j = i - 1; j >= 0; j --) {
if (isHuiWen(s.substring(j, i))) {
dp[i]++;
}
}
}
return dp[s.length()];
}
private boolean isHuiWen(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int longestPalindromeSubseq(String s) {
int len = s.length();
int[][] dp = new int[len][len + 1];
for (int i = len - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < len; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], Math.max(dp[i][j], dp[i][j - 1]));
}
}
}
return dp[0][len - 1];
}
|
双数组动态规划:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int maxProductPath(int[][] grid) {
long[][] dp = new long[grid.length][grid[0].length];
long[][] dp1 = new long[grid.length][grid[0].length];
dp[0][0] = grid[0][0];
dp1[0][0] = grid[0][0];
for (int i = 1; i < grid.length; i++) {
dp[i][0] = dp[i - 1][0] * grid[i][0];
dp1[i][0] = dp1[i - 1][0] * grid[i][0];
}
for (int i = 1; i < grid[0].length; i++) {
dp[0][i] = dp[0][i - 1] * grid[0][i];
dp1[0][i] = dp1[0][i - 1] * grid[0][i];
}
for (int i = 1; i < grid.length; i++) {
for (int j = 1; j < grid[0].length; j++) {
dp[i][j] = grid[i][j] > 0 ? Math.max(dp[i - 1][j], dp[i][j - 1]) * grid[i][j] : Math.min(dp1[i - 1][j], dp1[i][j - 1]) * grid[i][j];
dp1[i][j] = grid[i][j] > 0 ? Math.min(dp1[i - 1][j], dp1[i][j - 1]) * grid[i][j] : Math.max(dp[i - 1][j], dp[i][j - 1]) * grid[i][j];
}
}
return dp[grid.length - 1][grid[0].length - 1] >= 0 ? (int)(dp[grid.length - 1][grid[0].length - 1] % (1000000000 + 7)) : -1;
}
|
其实java支持多维数组 可以直接使用三维数组解决问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int maxProductPath(int[][] grid) {
long[][][] dp = new long[grid.length][grid[0].length][2];
dp[0][0][0] = grid[0][0];
dp[0][0][1] = grid[0][0];
for (int i = 1; i < grid.length; i++) {
dp[i][0][0] = dp[i - 1][0][0] * grid[i][0];
dp[i][0][1] = dp[i - 1][0][1] * grid[i][0];
}
for (int i = 1; i < grid[0].length; i++) {
dp[0][i][0] = dp[0][i - 1][0] * grid[0][i];
dp[0][i][1] = dp[0][i - 1][1] * grid[0][i];
}
for (int i = 1; i < grid.length; i++) {
for (int j = 1; j < grid[0].length; j++) {
dp[i][j][0] = grid[i][j] > 0 ? Math.max(dp[i - 1][j][0], dp[i][j - 1][0]) * grid[i][j] : Math.min(dp[i - 1][j][1], dp[i][j - 1][1]) * grid[i][j];
dp[i][j][1] = grid[i][j] > 0 ? Math.min(dp[i - 1][j][1], dp[i][j - 1][1]) * grid[i][j] : Math.max(dp[i - 1][j][0], dp[i][j - 1][0]) * grid[i][j];
}
}
return dp[grid.length - 1][grid[0].length - 1][0] >= 0 ? (int)(dp[grid.length - 1][grid[0].length - 1][0] % (1000000000 + 7)) : -1;
}
|