DP DFS EASY 2021.11.12

动态规划，关键是列出状态转移表格。

还要想清楚边界值。

class Solution {
    public int massage(int[] nums) {
        if (nums.length == 0){
            return 0;
        }
        if (nums.length == 1){
            return nums[0];
        }
        int[] max = new int[nums.length];
        int[] ans = new int[nums.length];
        max[0] = nums[0];
        max[1] = Math.max(nums[0], nums[1]);
        ans[0] = nums[0];
        ans[1] = nums[1];
        for (int i = 2; i < nums.length; i++){
            ans[i] = max[i - 2] + nums[i];
            max[i] = Math.max(max[i - 1], ans[i]);
        }
        return max[nums.length - 1];
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：35.5 MB, 在所有 Java 提交中击败了89.00%的用户

前序遍历：根左右。

class Solution {
    public ArrayList preorderTraversal(TreeNode root) {
        ArrayList res = new ArrayList();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List res){
        if (root == null){
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：36.7 MB, 在所有 Java 提交中击败了53.17%的用户

新知识

//动态数组声明,有括号
ArrayList A = new ArrayList();
//如果函数没有返回值，声明时用void
public void ...