动态规划
| 2 天前 | #32 最长有效括号 | 困难 | 1 次 |
|---|---|---|---|
| 2 天前 | #416 分割等和子集 | 中等 | 1 次 |
| 2 天前 | #152 乘积最大子数组 | 中等 | 1 次 |
| 5天前 | #300 最长递增子序列 | 中等 | 3 次 |
|---|---|---|---|
| 5 天前 | #139 单词拆分 | 中等 | 2 次 |
| 5 天前 | #322 零钱兑换 | 中等 | 5 次 |
| 5 天前 | #279 完全平方数 | 中等 | 1 次 |
| 5 天前 | #198 打家劫舍 | 中等 | 4 次 |
| 5 天前 | #118 杨辉三角 | 简单 | 1 次 |
| 5 天前 | #70 爬楼梯 | 简单 | 3 次 |
备注：
1、杨辉三角 注意边界条件的判断
2、打家劫舍 dp[1] = Math.max(nums[1] ,dp[0]); 的取值
3、完全平方数 第二层for int min = Integer.MAX_VALUE; 以及 min的赋值 以及 dp[i] 的赋值
4、零钱兑换 注意 边界条件 dp0的赋值 第二层for中 if的判断
5、单词拆分 注意初始化 dp0的值 这个是boolean的 dp
6、最长递增子序列 int max =1;
for(int i = 1; i< nums.length; i++){
for(int j = 0; j<i; j++){
if(nums[j] < nums[i]){ 直接背
7、乘积最大子数组 注意 定义最后结果时 要定义为Integer的最小值， 并且 imin 跟imax的比较 都是跟num[i]比较的
8、分割等和子集 的第二个 for、
for(int j = target; j>=nums[i]; j--){
dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i]);
}
9、最长有效括号 第二个else内的判断条件
stack.pop();
if(stack.isEmpty()){
stack.push(i);
}
res = Math.max(res,i- stack.peek());
# 爬楼梯
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];
}
}
思路：
1、经典动态规划，定义dp的时候 要n+1De
2、其余看题意分析
3、类似的还有斐波那契等。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 杨辉三角
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
for(int i = 0; i< numRows; i++){
List<Integer> item = new ArrayList<>();
for(int j = 0; j<=i; j++){
if(j == 0 || j==i){
item.add(1);
} else{
item.add(res.get(i-1).get(j-1)+ res.get(i-1).get(j));
}
}
res.add(item);
}
return res;
}
}
思路：
1、(res.get(i-1).get(j-1)+ res.get(i-1).get(j) 这个是这道题的精髓
2、就是先搞两层for 第二层 j<= I的 然后 if的判断 j==0跟j==i也就是两端的情况 就add（1）
3、其余else 就是动态规划 也就是 精髓所在 i-1 j-1 i-1 j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 打家劫舍
class Solution {
public int rob(int[] nums) {
if( nums.length == 1){
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(dp[0], nums[1]);
for(int i = 2; i< nums.length; i++){
dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[nums.length-1];
}
}
思路：
1、注意边界条件， 此题的dp是正常范围的
2、0 1 的位置要记录下来
3、从2循环
4、条件表达式也很明显 就是 后退两步+当前 或者 后悔1步 中的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 完全平方数
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
for(int i = 1; i<=n; i++){
int min = Integer.MAX_VALUE;
for(int j = 1; j*j <= i; j++){
min = Math.min(min, dp[i-j*j]);
}
dp[i] = min+1;
}
return dp[n];
}
}
思路：
1、此题的dp要+1的
2、dp中是以平方数作为缓存的， n在这是作为平方数的
3、min+1代表有一个的意思
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 零钱兑换
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;i++ ){
for(int j = 0; j< coins.length; j++){
if(coins[j] <=i){
dp[i] = Math.min(dp[i], dp[i-coins[j]]+1);
}
}
}
return dp[amount] > amount?-1:dp[amount];
}
}
思路：
1、dp[amount+1] 然后全都填充amount+1
2、之后遍历amount 然后便后coins 【背包问题】
3、如果 cons【j】 《= i 进行dp【i】的赋值 取最小 dp[i] = Math.min(dp[i], dp[i-coins[j]]+1);
4、最后的返回 也是要判断 dp[amount] > amount?-1:dp[amount]; 取最小 如果超过 返回 -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 单词拆分
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<String>(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(set.contains(s.substring(j, i)) && dp[j]){
dp[i] =true;
}
}
}
return dp[s.length()];
}
}
思路：
1、先去重
2、定义boolean的dp
3、然后 两层for
4、第二层for的条件 j<i && !dp[i]
5、 之后 如果 if(set.contains(s.substring(j, i)) && dp[j]) 当前的dp【i】才能是true 最后返回dp[length]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 最长递增子序列
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int max =1;
for(int i = 1; i< nums.length; i++){
for(int j= 0; j<i;j++){
if(nums[j]< nums[i]){
dp[i] = Math.max(dp[i], dp[j]+1);
}
max = Math.max(max, dp[i]);
}
}
return max;
}
}
思路：
1、定义dp 填充
2、定义max用于返回
3、然后两层for 动态规划这边的第二层for一般都还是j<i 的（或者可能加其他的）
4、 if(nums[j]< nums[i]){dp[i] = Math.max(dp[i], dp[j]+1);} 记录
5、最后对比max跟dp[i] 取最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 乘积最大子数组
class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE;
int imax = 1;
int imin = 1;
for(int i = 0; i< nums.length; i++){
if(nums[i]< 0){
int tmp = imax;
imax = imin;
imin = tmp;
}
imax = Math.max(imax*nums[i], nums[i]);
imin = Math.min(imin*nums[i], nums[i]);
max = Math.max(max, imax);
}
return max;
}
}
思路：
1、如上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 分割等和子集
class Solution {
public boolean canPartition(int[] nums) {
int sum =0;
for(int item: nums){
sum+=item;
}
if(sum%2==1){
return false;
}
int target = sum/2;
int[] dp = new int[target+1];
for(int i = 0; i<nums.length; i++){
for(int j = target; j>= nums[i]; j--){
dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i]);
}
if(dp[target] == target){
return true;
}
}
return dp[target] == target;
}
}
思路：
1、记录总和取中间数， 如果是奇数是不可能等和的 直接返回false
2、对中间数+1 建立dp
3、之后也是两层for 表达式也极为苛刻 理解背
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
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
# 最长有效括号
class Solution {
public int longestValidParentheses(String s) {
int max = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for(int i = 0; i< s.length();i++){
if(s.charAt(i) == '('){
stack.push(i);
} else{
stack.pop();
if(stack.isEmpty()){
stack.push(i);
}else {
max = Math.max(max, i-stack.peek());
}
}
}
return max;
}
}
思路：
1、此题利用栈做 简单些
2、注意思路的理解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
上次更新: 2024/03/26, 9:03:00