建设银行衡阳市分行网站,宁波建网站如何收费,网站需要哪些手续,wordpress 订阅号推送198、打家劫舍 状态转移方程 base case
边界问题就是#xff1a;走到最后一间房子门口也没抢#xff0c;那么最终抢到的金额为0
明确状态
“原问题和子问题中会变化的变量”
抢到的金额数就是状态#xff0c;因为随着在每一件房子门口做选择#xff0c;抢到的金额数会随…198、打家劫舍 状态转移方程 base case
边界问题就是走到最后一间房子门口也没抢那么最终抢到的金额为0
明确状态
“原问题和子问题中会变化的变量”
抢到的金额数就是状态因为随着在每一件房子门口做选择抢到的金额数会随之变化
确定选择
“导致状态变化的行为”
在每间房子门口都可以做出两个选择“抢”或者“不抢”。如果抢了的话那么下一间就不能抢如果这件不抢的话下一间就可以抢
定义dp函数
根据题意定义dp(n) 为n间房子能抢到的最大金额数
此外还要考虑从第几间房子开始抢。那么dp函数应该有两个参数从第几间房子开始-start可抢的房子数组-nums
那么状态转移方程就是
dp(nums,start) Math.max(nums[start] dp(nums,start 2),dp(nums,start 1));
//nums[start] dp(nums,start 2 表示从第start家开始抢抢到的金额自然是第start家的金额
//加上从start2家开始抢得到的金额
//dp(nums,start 1) 表示第start家不抢了从下一家开始抢 我们可以看到这里再次体现了 “[分解问题]的思路可以扩展成动态规划算法。” 我们把“从第start间房子开始抢到的金额”这个问题分解为“从下下间房子开始抢” 和 “从下一间房子开始抢” 两个子问题
有了状态转移方程我们就可以写出最基础的暴力递归解法了
暴力递归
class Solution {public int rob(int[] nums) {return dp(nums,0);}/*dp函数表示从第 start 间房子开始抢的最大金额*/int dp(int[] nums,int start){/*如果这排房子从头到尾都挑完了还没开始抢那就什么也抢不到*///base caseif(start nums.length){return 0;}/*在每个房子门前有两种选择抢 / 不抢*/int res Math.max(nums[start] dp(nums,start2), dp(nums,start1));return res;}
}
这种解法显然时间复杂度太高。按照我们之前所讲的通过处理“重叠子问题”来降低时间复杂度
使用了备忘录的从上到下的递归解法
class Solution {public int rob(int[] nums) {int[] memo new int[nums.length];//初始化备忘录数组Arrays.fill(memo,-1);return dp(nums,0,memo);}int dp(int[] nums,int start,int[] memo){//base caseif(start nums.length){return 0;}//如果备忘录中存有这个数值就直接取用if(memo[start] ! -1){return memo[start];}//状态转移方程memo[start] Math.max(dp(nums,start1,memo),nums[start] dp(nums,start2,memo));return memo[start];}
}
问题1如何判断该问题是否能够优化
根据前面的文章我们已将知道我们可以通过优化“重叠子问题”来降低时间复杂度。那么我们怎么才能知道是否存在“重叠子问题”呢 抽象出递归框架先找出 [状态] 然后根据递归框架看看如果从一个状态转移到另一个状态有不止一条路径那么说明存在 [重叠子问题] 使用了dp数组的从下到上的迭代解法
class Solution {/*从下到上的迭代数组解法*/public int rob(int[] nums) {int n nums.length;//为什么数组长度定义为 n2/*dp[i] 表示从第 i 家开始抢劫获得的金额数0~n*/int dp[] new int[n 2];for (int i n-1; i 0; i--) {dp[i] Math.max(nums[i] dp[i2],dp[i1]);}return dp[0];}
}
问题1为什么dp数组长度定义为 n 2呢
因为dp[i] 与dp[i2] 和dp[i1]有关为了防止数组越界将数组长度定为n2 如果有什么不明白或者文章中内容有误请在评论区留言。我看到后会一一回复。 及时收获反馈这对我很重要。
