动态规划习题其七【力扣】【算法学习day.29】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.统计放置房子的方式数

题目链接:2320. 统计放置房子的方式数 - 力扣（LeetCode）

题面:

代码:

class Solution {
    int mod = 1000000007;
    long[] arr;
    public int countHousePlacements(int n) {
        arr = new long[n+1];
        Arrays.fill(arr,-1);
       long ans = recursion(n);
       return (int)((ans*ans)%mod);
    }
    public long recursion(int n){
        if(n<=0)return 1;
        if(arr[n]!=-1)return arr[n];
        return arr[n] =(recursion(n-1)%mod+recursion(n-2)%mod)%mod;
    }
}

2.打家劫舍II

题目链接:213. 打家劫舍 II - 力扣（LeetCode）

题面:

代码:

class Solution {
    int[] arr;
    int[] brr;
    int[] nums;
    int n;
    public int rob(int[] nums) {
        if(nums.length==1)return nums[0];
        this.nums = nums;
         n = nums.length;
        arr = new int[n+1];
        brr = new int[n+1];
        Arrays.fill(arr,-1);
        Arrays.fill(brr,-1);
        return Math.max(recursion(n-1),recursion2(n-1));
    }
    public int recursion(int i){
        if(i<0)return 0;
        if(arr[i]!=-1)return arr[i];
        if(i==n-1)return recursion(i-1);
        return arr[i] = Math.max(recursion(i-1),recursion(i-2)+nums[i]);
    }
     public int recursion2(int i){
        if(i<=0)return 0;
        if(brr[i]!=-1)return brr[i];
        if(i==n-1)return recursion2(i-2)+nums[i];
        return brr[i] = Math.max(recursion2(i-1),recursion2(i-2)+nums[i]);
    }
}

3.施咒的最大总伤害

题目链接:3186. 施咒的最大总伤害 - 力扣（LeetCode）

题面:

代码:

class Solution {
    public long maximumTotalDamage(int[] power) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : power) {
            cnt.merge(x, 1, Integer::sum);
        }

        int n = cnt.size();
        int[] a = new int[n];
        int k = 0;
        for (int x : cnt.keySet()) {
            a[k++] = x;
        }
        Arrays.sort(a);

        long[] memo = new long[n];
        Arrays.fill(memo, -1);
        return dfs(a, cnt, memo, n - 1);
    }

    private long dfs(int[] a, Map<Integer, Integer> cnt, long[] memo, int i) {
        if (i < 0) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        int x = a[i];
        int j = i;
        while (j > 0 && a[j - 1] >= x - 2) {
            j--;
        }
        return memo[i] = Math.max(dfs(a, cnt, memo, i - 1), dfs(a, cnt, memo, j - 1) + (long) x * cnt.get(x));
    }
}