Skip to content

Commit f2431df

Browse files
znn0301znn0301
committed
dp-3
1 parent ceed111 commit f2431df

File tree

14 files changed

+881
-2
lines changed

14 files changed

+881
-2
lines changed

‎src/main/java/com/chen/algorithm/study/test279/Solution.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,11 +8,11 @@ public class Solution {
88

99

1010
public int numSquares(int n) {
11-
1211
int[] dp = new int[n + 1];
12+
1313
for (int i = 1; i <= n; i++) {
1414
dp[i] = i;
15-
for (int j = 0; i - j * j >= 0; j++) {
15+
for (int j = 1; i - j * j >= 0; j++) {
1616
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
1717
}
1818
}

‎src/main/java/com/chen/algorithm/znn/dynamic/test198/Solution.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package com.chen.algorithm.znn.dynamic.test198;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
7+
*
8+
* @Auther: zhunn
9+
* @Date: 2020/11/6 17:16
10+
* @Description: 打家劫舍：1-动态规划；2-动态规划 + 滚动数组
11+
*/
12+
public class Solution {
13+
14+
/**
15+
* 1-动态规划
16+
* 1. 偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。
17+
* 2. 不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。
18+
*
19+
* @param nums
20+
* @return
21+
*/
22+
public int rob(int[] nums) {
23+
if (nums == null || nums.length == 0) {
24+
return 0;
25+
}
26+
int len = nums.length;
27+
if (len == 1) {
28+
return nums[0];
29+
}
30+
31+
int[] dp = new int[len]; // dp[i] 表示前 ii 间房屋能偷窃到的最高总金额
32+
dp[0] = nums[0];
33+
dp[1] = Math.max(nums[0], nums[1]);
34+
35+
for (int i = 2; i < len; i++) {
36+
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
37+
}
38+
return dp[len - 1];
39+
}
40+
41+
public int rob2(int[] nums) {
42+
if (nums == null || nums.length == 0) {
43+
return 0;
44+
}
45+
int len = nums.length;
46+
if (len == 1) {
47+
return nums[0];
48+
}
49+
50+
int first = nums[0], second = Math.max(nums[0], nums[1]);
51+
for (int i = 2; i < len; i++) {
52+
int temp = second;
53+
second = Math.max(first + nums[i], temp);
54+
first = temp;
55+
}
56+
return second;
57+
}
58+
59+
@Test
60+
public void test() {
61+
int[] nums = {2, 7, 9, 3, 1};
62+
System.out.println(rob2(nums));
63+
}
64+
}

‎src/main/java/com/chen/algorithm/znn/dynamic/test213/Solution.java‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package com.chen.algorithm.znn.dynamic.test213;
2+
3+
import org.junit.Test;
4+
5+
import java.util.Arrays;
6+
7+
/**
8+
* @Auther: zhunn
9+
* @Date: 2020/11/6 17:45
10+
* @Description: 打家劫舍 II：在198题的基础上，选择不偷第一家或不偷最后一家
11+
*/
12+
public class Solution {
13+
14+
public int rob(int[] nums) {
15+
if (nums == null || nums.length == 0) {
16+
return 0;
17+
}
18+
int len = nums.length;
19+
if (len == 1) {
20+
return nums[0];
21+
}
22+
return Math.max(myRob(Arrays.copyOfRange(nums, 0, len - 1)),
23+
myRob(Arrays.copyOfRange(nums, 1, len)));
24+
25+
}
26+
27+
private int myRob2(int[] nums) {
28+
int len = nums.length;
29+
int[] dp = new int[len];
30+
dp[0] = nums[0];
31+
dp[1] = Math.max(nums[0], nums[1]);
32+
33+
for (int i = 2; i < len; i++) {
34+
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
35+
}
36+
return dp[len - 1];
37+
}
38+
39+
private int myRob(int[] nums) {
40+
int first = nums[0], second = nums[1];
41+
for (int i = 2; i < nums.length; i++) {
42+
int temp = second;
43+
second = Math.max(first + nums[i], temp);
44+
first = temp;
45+
}
46+
return second;
47+
}
48+
49+
@Test
50+
public void test() {
51+
int[] nums = {1, 2, 3, 1};
52+
System.out.println(rob(nums));
53+
}
54+
}

‎src/main/java/com/chen/algorithm/znn/dynamic/test279/Solution.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package com.chen.algorithm.znn.dynamic.test279;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* @Auther: zhunn
7+
* @Date: 2020/11/5 18:00
8+
* @Description: 完全平方数：1-动态规划
9+
*/
10+
public class Solution {
11+
12+
public int numSquares(int n) {
13+
14+
int[] dp = new int[n + 1];
15+
//dp[0] = 0; //题意是给定正整数，不用考虑0
16+
17+
for (int i = 1; i <= n; i++) {
18+
dp[i] = i;
19+
for (int j = 1; i - j * j >= 0; j++) {
20+
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
21+
}
22+
}
23+
return dp[n];
24+
}
25+
26+
@Test
27+
public void test() {
28+
System.out.println(numSquares(9));
29+
}
30+
}

‎src/main/java/com/chen/algorithm/znn/dynamic/test322/Solution.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@
1212
* @Auther: zhunn
1313
* @Date: 2020/11/4 22:03
1414
* @Description: 零钱兑换：1-动态规划；2-动态规划-优化空间
15+
* 返回所需的最少的硬币个数
1516
*/
1617
public class Solution {
1718

‎src/main/java/com/chen/algorithm/znn/dynamic/test337/Solution.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.chen.algorithm.znn.dynamic.test337;
2+
3+
import com.chen.algorithm.znn.tree.TreeNode;
4+
import org.junit.Test;
5+
6+
/**
7+
* https://leetcode-cn.com/problems/house-robber-iii/solution/shu-xing-dp-ru-men-wen-ti-by-liweiwei1419/
8+
*
9+
* @Auther: zhunn
10+
* @Date: 2020/11/6 18:35
11+
* @Description: 打家劫舍 III：1-树的后序遍历；
12+
*/
13+
public class Solution {
14+
15+
public int rob(TreeNode root) {
16+
int[] res = dfs(root); // 树的后序遍历
17+
return Math.max(res[0], res[1]);
18+
}
19+
20+
private int[] dfs(TreeNode root) {
21+
if (root == null) {
22+
return new int[]{0, 0};
23+
}
24+
25+
int[] left = dfs(root.left); // 分类讨论的标准是：当前结点偷或者不偷
26+
int[] right = dfs(root.right); // 由于需要后序遍历，所以先计算左右子结点，然后计算当前结点的状态值
27+
28+
29+
int[] res = new int[2]; // dp[0]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点不偷; dp[1]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点偷
30+
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
31+
res[1] = root.val + left[0] + right[0];
32+
return res;
33+
}
34+
35+
@Test
36+
public void test() {
37+
TreeNode left = new TreeNode(2, null, new TreeNode(3));
38+
TreeNode right = new TreeNode(3, null, new TreeNode(1));
39+
TreeNode root = new TreeNode(3, left, right);
40+
System.out.println(rob(root));
41+
}
42+
}

‎src/main/java/com/chen/algorithm/znn/dynamic/test343/Solution.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package com.chen.algorithm.znn.dynamic.test343;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
7+
*
8+
* @Auther: zhunn
9+
* @Date: 2020/11/5 18:46
10+
* @Description: 整数拆分
11+
*/
12+
public class Solution {
13+
14+
public int integerBreak(int n) {
15+
if (n < 2) {
16+
return n;
17+
}
18+
19+
int[] dp = new int[n + 1]; // dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积
20+
dp[0] = 0;
21+
dp[1] = 1;
22+
23+
for (int i = 2; i <= n; i++) {
24+
for (int j = 1; j < i; j++) {
25+
dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, (i - j) * j)); // 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
26+
// 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]。
27+
}
28+
}
29+
return dp[n];
30+
}
31+
32+
33+
@Test
34+
public void test() {
35+
System.out.println(integerBreak(2));
36+
System.out.println(integerBreak(10));
37+
System.out.println(integerBreak(58));
38+
}
39+
}

0 commit comments

Comments
 (0)