动态规划1------打家劫舍
May 2020
MAY I LOVE YOU
在五月，期待一个美好夏天
题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
题解
一直想把动态规划问题刷的差不多在做题注，事实上不太可能，所以还是一点一点做算了，对于动态规划问题其实就是要构建动态转移方程就完事了，问题时如何构造，变量是什么很关键
一般动态转移方程的变量是从一个数组中的序列号来确定的，举一个简单例子，就是一个数组的前k个值的一种规律应该是怎么样的f(k) = ?，比如最大多少最小多少，这是非常舒服的一种思考方式，然后用后面的方法来递推f(k+1)应该怎么样，这种和斐波那契数列基本上高度吻合， 这道题可以这么做，这道题是第五类动态规划问题：取舍决定（当前元素取或是不取），动态转移方程：
取舍决定（当前元素取或是不取）
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= k; ++j) {
dp[i][j] = max({dp[i][j], dp[i-1][j] + arr[i], dp[i-1][j-1]});
dp[i][j-1] = max({dp[i][j-1], dp[i-1][j-1] + arr[i], arr[i]});
}
}
是取还是舍取决于max的值，我们是不知道对应的序列的，也不需要知道，只要把它的值算出来就行了， 如果一直拘泥于他的排序选取方式，动态规划思路就会受限制。
。为了保证代码的连贯性，准备一直采用c++的编写环境了。
这里我们初始设置一个动态规划数组dp, dp[0] = 0; dp[1] = nums[0], 假设已知dp[k]， 那么dp[k+1] = max(dp[k-1]+nums[k], dp[k]), 就是末尾几个dp值做一下对比就行了，和斐波那契数列基本上没什么区别
class Solution {public:int rob(vector<int>& nums) {vector<int> dp(nums.size()+1, 0);if(nums.size() <= 0)return 0;else if(nums.size() == 1)return nums[0];dp[0] = 0;dp[1] = nums[0];for (int i = 2; i <= nums.size(); ++i) {dp[i] = max(dp[i-2]+nums[i-1], dp[i-1]);}return dp[nums.size()];}};