LeetCode30刷-动态规划_leetcode 30

本篇为LeetCode30刷，记录个人学习记录，如果错误欢迎致信，后续会补充

动态规划

No.1 一维（首尾不相连）

动态规划无非就是记录一下每一步的最优解，不需要用到递归，但是需要找到初始值，推算出下一个数由前几个数运算出来的公式

package Leetcode;

public class 动态规划_打家劫舍 {
    public static void main(String[] args) {
        int[] nums = new int[]{2,7,9,3,3};
        System.out.println(dp(nums));
    }
    //动态规划-----没有用到递归，只是记忆化数组，记录每一步的最优解
    public static int dp(int[] nums){
        int len = nums.length;
        if(nums == null || len == 0){
            return 0;
        }
        if(len == 1){
            return nums[0];
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2;i < len;i++){
            dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i]);
        }
        return dp[len - 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

No.2 首尾相连
情况1：拿第一个，不拿最后一个
情况2：不拿第一个，那最后一个

package Leetcode;

public class 动态规划_打家劫舍 {
    public static void main(String[] args) {
        int[] nums = new int[]{2,7,9,3,3};
        System.out.println(Math.max(dp1(nums,0,nums.length - 2),dp1(nums,1,length - 1));
    }

    //下面使用了空间优化，采用两个值来存储最优解，优化了空间结构
    public static int dp1(int[] nums,int start,int end){
        int len = nums.length;
        if(nums == null || len == 0){
            return 0;
        }
        if(len == 1){
            return nums[0];
        }
        int first = nums[0],second = Math.max(nums[0],nums[1]);
        for(int i = start + 2;i <= end;i++){
            int temp = second;
            second = Math.max(second,first + nums[i]);
            first = temp;
        }
        return second;
    }
}

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

No.3 二叉树

工具类

package Leetcode.tools;


public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public int deep;
    public TreeNode(){}
    public TreeNode(int val){this.val = val;}
    public TreeNode(int val, TreeNode left,  TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right;
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

主函数

package Leetcode;

import Leetcode.TreeNode;

public class 动态规划_打家劫舍 {
    public static void main(String[] args) {
        TreeNode node5 = new TreeNode(1,null,null);
        TreeNode node4 = new TreeNode(3,null,null);
        TreeNode node3 = new TreeNode(3,null,node5);
        TreeNode node2 = new TreeNode(2,null,node4);
        TreeNode node1 = new TreeNode(3,node2,node3);
        int[] arr = dfs(node1);
        System.out.println(Math.max(arr[0],arr[1]));



    }
    public static int[] dfs(TreeNode node){
        if(node == null){
            return new int[]{0,0};
        }
        //l和r中元素的含义：l[0]表示选,l[1]表示不选
        //dfs搜索到最底部，从下往上开始分析，给l和r赋值
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        //如果选择这个点，则它的下面两个点不能再选
        int select = node.val + l[1] + r[1];
        //如果不选择当前点，则他的下面两个点可以选或不选
        int noselect = Math.max(l[0],l[1]) + Math.max(r[0],r[1]);
        return new int[]{select,noselect};

    }
}

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