动态规划
198.打家劫舍
题目描述:
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
思路:
这题看的题解，其中最让我印象深刻的就是关于子问题的定义：子问题是和原问题相似，但规模较小的问题，我们这里的原问题是：在某些限制条件下，求出盗窃n间房子的最高金额，也就是说，我们可以理解为在前n间房子中盗窃的最大金额。所以我们在这里所定义的子问题就可以是：dp[i]代表在前i间房子中所盗窃的最高金额。
有了这个定义后，对于每一个子问题，我们的解决方法就是，如果说它前一个屋子被偷了，那么它本身这个屋子就不能偷了，所以最大金额就是dp[i-1],如果它前面那个屋子没被偷，那么它的最大金额就是它本身的前两个屋子的最大金额加上本身房子的金额，也就是dp[i-2]+nums[i]。于是前i间屋子中所盗窃的最高金额就应该是前两种方式的最大金额，也就是Max{dp[i-1],dp[i-2]+nums[i]}.
我们看这里的边界条件，也就是第一间房和第二间房的时候，第一间房因为只有一间，所以最大盗窃金额就是nums[0],第二间房的盗窃金额为Max{nums[0],nums[1]}
关键代码
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
}
213.打家劫舍2
题目描述：
这道题是在上一道的基础上加了一个条件，所有的房子围成了一个圈。
思路：
这道题的思路和上道题类似，不过有一个不同点就是所有的房子连成了一个圈，所以当第一个房子被偷的时候，最后一个房子就不能偷，当第一个房子不被偷的时候，最后一个房子就不能偷。
所以我们可以分为两种情况。
第一种是第一个房子被偷时，这个时候我们的dp[0]=nums[0],dp[1]=max{dp[0],nums[1]},此时我们不考虑最后一个房子，即我们考虑的所有房子范围为[0,n-2]。关键代码是：
for (int i = 2; i < len-1; i++) {
//偷
dp2[i] = Math.max(dp2[i-1],dp2[i-2]+nums[i]);
maxValue = Math.max(maxValue,dp2[i]);
}
第二种是第一个房子不被偷的时候，这时有dp[0]=0,dp[1]=max{dp[0],nums[1]}，此时最后一个房子可能被偷，于是范围是[1,n-1]，关键代码为：
for (int i = 2; i < len; i++) {
//不偷
dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i]);
maxValue = Math.max(maxValue,dp1[i]);
}
然后我们使用一个标志来记录两种情况中的最大值就可以了。
740删除并获得点数
题目描述：
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
思路：
看得题解，确实没想到这个可以用打家劫舍的思路来做。
这个题它的要求是，如果一个数被选了，那么它左边和右边的数都不能被选，这一点其实是和打家劫舍不能抢劫相连的两间房是类似的。
所以说我们可以构造类似的一个数组arr,arr[i]表示选择i点可以获得的点数，对应打家劫舍里面也就是每个房间所能抢的钱。
构造完这个数组之后，我们就可以写出跟打家劫舍类似的状态转移方程（这里dp的定义是类似的），dp[i] = Math.max(dp[i-1],dp[i-2]+arr[i]*i),为什么这里的arr[i]要乘i呢，因为我们这里的arr[i]代表的是下标为i的数被操作的次数,但是实际上我们所求的dp是点数，所以我们需要将次数乘以点数，才是这个数的点数和。
这里的初始值的dp[0]=0,如果dp[1]存在的话有dp[1]=Math.max(dp[0],arr[1])。关键代码：
for (int i = 2; i < max+1; i++) {
dp[i] = Math.max(dp[i-1],dp[i-2]+arr[i]*i);
}