思想总结

  1. 注意转移方程一般是判断是否选择当前情况，来由前一个或前几个状态转移来
  2. 注意不要上来就盲目定义 dp 的子问题，有可能需要先拆解一层，才能定义 dp 的子问题

    代表题目

    198.打家劫舍

    你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

1. 首先定义子问题：

定义子问题为打劫前 n 间房子能窃取到的最高金额，定义 dp[nums.len + 1]，；注意此时的 dp 数组已经比原问题给定的数组长度大1了，因为存在了 dp[0] 这一状态，即打劫前 0 间房子

这里其实题目没有打劫的顺序要求， 但是为了更好的解决问题因，此定义了前 n 间即从左到右了

2. 写出初始条件：

  • dp[0] = 0 没有一间房子肯定是0

  • dp[1] = nums[0] 只有一间房子肯定是第一间房子的钱

    3. 根据约束条件写状态转移方程

    dp[n] 代表偷前 n 个房间，那么可以偷当前房间也可以不偷，由于不能连续偷：

  • 如果不偷当前房间，那么 dp[n] 就等于 dp[n-1]

  • 如果偷当前房间，则不能偷前一个房间；dp[n] 就等于 dp[n-2] + nums[n-1] （此时注意和 nums 的对应关系）

dp[n] = max(dp[n-2]+nums[n-1], dp[n-1]);

213.打家劫舍 II

相比上面的问题，房屋是围成一圈的，条件依旧是不能偷相邻的

此时多了一个约束条件，偷第一家，就不能偷最后一家；此时不能掉入一步写成转移方程的死胡同，可以将问题先粗粒度的拆解一层：

  1. 偷第一家，则肯定不能偷最后一家
  2. 不偷第一家，则可以偷最后一个（注意是可以，最终偷不偷最后一个还要看动态规划的结果）

此时，是不是只要调用两次“198.打家劫舍”里的递推函数就可以了🙂，然后再取这两者最大的就行啦

  1. int first = robRange(nums, 0, n-2);
  2. int second = robRange(nums, 1, n-1);
  3. return Math.max(first, second);

740. 删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。 每次操作中，选择任意一个 nums，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

看似是一道新题，但是仍然是“198.打家劫舍”，看题目给的一个提示：

输入：nums = [2,2,3,3,3,4] 输出：9 解释： 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。 总共获得 9 个点数。

2 3 4 相邻，选了 3 就不能选 2 和 4。此时还是不能掉入一步写成转移方程的死胡同，可以将问题先转化一层，将题目给的数组转化成打家劫舍的数组，假设 nums 中有 Cx 个 nums[i] 则:

  • sums[x] = Cx * num[i], num[i] 都是等于 x 的
  • sums[x] = 0, 那些 num[i] 里没有的, 当然就是 0 了

然后再调用“198.打家劫舍”的递推公式就行啦