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

力扣动态规划-4【算法学习day.98】

article 2025/1/20 14:53:28

前言

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

习题

1.删除并获得节点

题目链接:740. 删除并获得点数 - 力扣（LeetCode）

题面:

附上宫水大佬代码:

class Solution {
    int[] cnts = new int[10010];
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        int max = 0;
        for (int x : nums) {
            cnts[x]++;
            max = Math.max(max, x);
        }
        // f[i][0] 代表「不选」数值 i；f[i][1] 代表「选择」数值 i
        int[][] f = new int[max + 1][2]; 
        for (int i = 1; i <= max; i++) {
            f[i][1] = f[i - 1][0] + i * cnts[i];
            f[i][0] = Math.max(f[i - 1][1], f[i - 1][0]);
        }
        return Math.max(f[max][0], f[max][1]);
    }
}

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

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

题面:

代码:

class Solution {
    int[][] flag;
    int mod = (int)1e9 + 7;
    public int countHousePlacements(int n) {
        flag = new int[n+1][2];
        flag[0][1] = 1;
        flag[0][0] = 1;
        for(int i = 1;i<n;i++){
            flag[i][0] = (flag[i-1][0]+flag[i-1][1])%mod;
            flag[i][1] = flag[i-1][0];
        }
        long ans = (flag[n-1][0] + flag[n-1][1])%mod;
        long f = (ans*ans)%mod;
        return (int)f;
    }
}