删除游戏-类似打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

1 熟悉打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例：

        根据题目中获取最高金额，而且是否打劫第i家，取决于第i-1家是否打劫。很明显这个是一个动态规划问题。我们需要定义状态转移方程。 

其中

dp[0][i]：表示未偷取第i家时候取得的最大值

dp[1][i]：表示偷取第i家时候取得的最大值。

那么代码就可以写为：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        // dp[0][i]：表示不打劫第i家能够获取的最大资源
        // dp[1][i]：表示打劫第i家能够获取的最大资源
        int[][] dp = new int[2][n + 1];

        for (int i = 1; i <= n; i++) {
            dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1]);
            dp[1][i] = dp[0][i - 1] + nums[i - 1];
        }
        return Math.max(dp[0][n], dp[1][n]);
    }
}

 类似的也有一个删除游戏：题目如下

题目详情 - 2022.9.13-删除游戏 - Hydro (codefun2000.com)

根据题目解析，相当于偷完第i家，不能偷第i-1和第i+1家了，那么们从小到大遍历就不用考虑这i+1家了。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main19 {

    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(cin.readLine());
        int N = 100001;
        int[] arr = new int[N];
        int[] cnt = new int[N];
        String[] split = cin.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(split[i]);
            cnt[arr[i]]++;
        }
        // dp[0][i] 表示，只考虑不大于i的数，并且没有操作等于i的数的最高得分
        // dp[1][i] 表示只考虑不大于i的数，并且操作了所有等于i的数的最高得分
        int[][] dp = new int[2][N];

        for (int i = 1; i <= 100000; i++) {
            // 没有偷第i家的最大值为：max(没有投第i-1,偷了第i-1)
            dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1]);
            //偷了第i家的最大值为，没有偷第i-1家 + 投了第i家
            dp[1][i] = dp[0][i - 1] + i * cnt[i];
        }
        System.out.println(Math.max(dp[0][100000],dp[1][100000]));
    }
}