动态规划

题目

数组 取不相邻的数之和 最大的情况

例1 数组[1,2,4,1] 最大情况 1+4=5

例2 数组[1,2,9,3,2] 最大情况 1+9+2=12

    public static void main(String[] args) {

    //        System.out.println(rec(nums.length-1));
    
    //        Arrays.fill(cache, -1);//成员预先置为-1
    //        System.out.println(rec2(nums.length - 1));

        System.out.println(rob(nums));
    }

    static int[] nums = {1, 2, 9, 3, 2};

    //递归操作
    public static int rec(int index) {
        if (index == 0) {
            return nums[0];
        }
        if (index == 1) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(rec(index - 2) + nums[index], rec(index - 1));
    }

    //递归问题  重复性操作
    static int[] cache = new int[nums.length];

    public static int rec2(int index) {
        if (index == 0) {
            return nums[0];
        }
        if (index == 1) {
            return Math.max(nums[0], nums[1]);
        }
        if (cache[index] != -1) {
            return cache[index];
        }
        int max = Math.max(rec(index - 2) + nums[index], rec(index - 1));
        cache[index] = max;
        return max;
    }

    //基本上所有的动态规划都可以由递归进行转换
    //动态规划思想  将大规模转换为小规模
    //f(index) = max(f(index-1),f(index-2)+nums[index])
    public static int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[dp.length - 1];
    }
    //优化空间复杂度
    public static int rob2(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int pre1 = nums[0];
        int pre2 = Math.max(nums[0], nums[1]);
        int res = pre2;
        int[] dp = new int[nums.length];
        for (int i = 2; i < nums.length; i++) {
           res = Math.max(pre2, pre1 + nums[i]);
           pre1 = pre2;
           pre2 = res;
        }
        return res;
    }