算法-动态规划（二）
今天继续我们的动态规划专题，集中练习一些有关动态规划的题，加深印象。
👉👀💬今日练习（一）打家劫舍（LeetCode-198）。
去偷沿街的房屋，且每个屋里都有数量不等的钱，用数组nums来表示所有屋里的金额。
注意，如果偷相邻两个屋就会触发报警，计算在不触发报警的情况下，你一晚最多能偷到多少，返回最大值。如：
输入：[1,2,3,1]输出：4--------------输入：[2,7,9,3,1]输出：12=2+9+1
🙇思路：
依旧是动态规划，还是我们之前强调的：
定义子问题，
找出状态转移，即子问题的递推关系
确定【填表】的计算顺序
空间优化，这前期可以先放一放，等熟练了在来考虑。
一、定义子问题
什么是子问题？子问题是和原问题相似，但规模较小的问题。本题求解从所有屋里可以盗取的最大金额，子问题就是，“从K个屋里能偷到的最大金额”。我们定义子问题参数为k，如果有n个房屋的话，就一共有n个子问题，动态规划就是要求这一堆子问题的解。
动态规划要求有两个性质：
原问题可由子问题表示，否则求半天得不到原文那就很尴尬了。这道题中，n=k，就是原问题。
一个子问题也可以由其他子问题来得到。如这道题里，f(k)可以由f(k-1)和f(k-2)来得到，至于为什么我们放后面来讲。
满足以上两个性质，一般就可以用动态规划来求解。
二、写出递推关系（状态转移）。
这一步是动态规划的核心，也是难点，如果我们找不到递推关系，那么动态规划也没戏。
我们来分析此题：
假设有n个屋，屋里的金额分别是nums[0]、nums[1]、nums[2]···nums[n-1]、nums[n]，第k个屋里的金额为nums[k-1]，子问题f(k)表示从前k个屋能偷到的最大金额，偷前k个屋，有以下两种方案：
偷第k个屋，那第k-1个屋就不能偷，否则会报警，所以
f(k)=nums[k-1]+f(k-2)。
不偷第k个屋，所以我们可以偷前k-1个屋，所以f(k)=f(k-1)。
综上两步，偷前k个屋，最大金额为：
f(k)=max(f(k-1) , nums[k-1]+f(k-2)，也填上了上文中所说的f(k)由f(k-1)f(k-2)决定的坑。在写递推关系的时候，要注意k=0时，f(0)=0；k=1时f(1)=nums[0]。
三、确定【填表】的计算顺序。
一般情况下动态规划都是自低而上的的计算顺序。
代码：
public int rob(int[] nums){int len=nums.length;if(len <1){return 0;}if(len<2){return nums[0];}int[] dp = new int[len+1];dp[0]=0;dp[1]=nums[0];for(int k=2;k<=len;k++){dp[k]=Math.max(dp[k-1],nums[k-1]+dp[k-2]);}return dp[len];}
复杂度分析
时间复杂度：O(N)，需要到nums全部遍历一次。
空间复杂度：O(N)，我们需要用dp数组来保存所有的过程值。
四、空间优化。
在上面解法中我们需要一个len+1长的数组dp来保存所有的过程值，但核心代码：dp[k]=Math.max(dp[k-1],nums[k-1]+dp[k-2]);代码里我们只关系dp[k-1]和dp[k-2]这两个值，其他位置的值是啥，我们并不关心，也无需保存，所以这就是我们优化的点，我们可以仅用O(1)的空间就可以解决。
代码：
public int rob_1(int[] nums){int len=nums.length;if(len <1){return 0;}if(len<2){return nums[0];}int prev=nums[0];int curr=Math.max(prev,nums[1]);for(int k=2;k<len;k++){int temp = curr;curr= Math.max(curr,nums[k]+prev);prev=temp;}return curr;}
复杂度分析
时间复杂度：O(N)，需要到nums全部遍历一次。
空间复杂度：O(N)，我们只保存了前两个房屋的最大金额。
不积跬步，无以至千里。
文章有帮助的话，点个转发、在看呗
。
谢谢支持哟 (*^__^*)
END
👇