当前位置：首页 > news >正文

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

news 2024/11/25 5:52:04

前言

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

习题

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));}
}