可以做微课PPT模板 网站,惠州市两学一做网站,常州网站关键词推广,建设网站参数198. 打家劫舍 - 力扣#xff08;LeetCode#xff09;
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#…198. 打家劫舍 - 力扣LeetCode
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
示例 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 。提示1 nums.length 100
0 nums[i] 400
算法设计 我们是如何辨识出这道题需要使用dp算法的呢 首先我们需要理解题意题目讲述的是一个实际问题我们需要进行一些数学抽象层层刨析的看到问题的本质。 首先我们应该看到第一层题目中虽然只说了相邻房间不能同时打劫但是我们应该理解为不能打劫相邻房间但打劫的房间不一定是以间隔1的形式出现的也可以跳跃多个房间打劫下一个。 接着上面我们应该分析出第二层问题虽然简单描述但是可以想象为被相邻规则直接禁止的房屋我们不能踏入花园而未被相邻规则禁止的房屋我们可以到花园外看两眼决定是否进行打劫。 接下来我们通过目前的状态推测过去的情况对于到达第i个房屋后的能打到的最大金额dp[i] 1.当我们目前选择了打i时之前绝对不可能打过i-1所以有dp[i] dp[i-2] nums[i] 2.当我们不打i时无非两种情况一种确实打过了i-1所以不能打i二种没打i-1但是也不计划打i以上两种情况都可以用dp[i-1]来概括然而究竟打不打i-1这个需要根据dp[i-1]的相同方法分析才能得到也就是递推 综上所述为了在每个dp求得最大的金额我们应该有状态转移方程 dp[i] fmax(dp[i-2]nums[i], dp[i-1]) 这样我们就分析出它跟爬楼梯问题的一个共通点了就是达到i时的状态都可以通过拆解为多种过去状态分支。再把过去状态与dp进行联系从而求得dp[i]
int rob(int* nums, int numsSize) {int dp[2];int temp;dp[0]*(nums);if(numsSize1){return dp[0];}if(numsSize1){dp[1]fmax(dp[0],*(nums1));}if(numsSize2){for(int i2; inumsSize; i){tempfmax(dp[0]*(numsi),dp[1]);dp[0]dp[1];dp[1]temp;}}return dp[1];
} 比如说如果我打了i的那么我最近至少也得从dp[i-2]过来吧 再比如我不打i要么是因为我打了i-1所以不能打i再要么是我不打i-1只是在它门口鬼鬼祟祟地晃悠了两圈又来到i其实我能打i但是仔细考虑了一下不打i。 所以从语态角度讲这道题的状态转移条件划分规则为在一般现在时下是否打i而不是我是否能打i。所以打劫Ⅰ类问题与爬楼梯的区别在于爬楼梯中状态转移方程的dp [i-1] 和 dp[i-2]爬到dp[i]讲的是一个can的问题描述了我上一次状态到本次状态的能力。而在打劫问题中我们描述的是一个do的问题以基本实时的分支为标准进行划分而通过对对立事件二存一的逻辑求得dp[i]。 为什么在打劫问题中需要以do的方式去思考呢在以后我们如何从根本上辨别这两种状态转移方式的应用场景 以我看呀爬楼梯问题的目标解是达成目的途径数量所以计算过程本质是把所有最简对立事件的个数统计。而打劫问题是一个结果驱动型问题要求的是给定过程量的和最大结果所对应的行为是固定的一种或多种。 不如我们先换一个问法在题设条件下不追求最大获利总共有多少种打劫方式 假设dp_can[i]表示打劫到i总共的方式 那么打劫到i有i种大可能性即上一次打劫的是01...i-1 那么 dp_can[i] dp_can[i-2] ... dp_can[0] 很显然dpcan[0]1因为打1只有小区大门开始一种方法 dpcan[1]1; dpcan[2] dpcan[0] 1; dpcan[3] dpcan[0] dpcan[1] 2; ... 因此这更像是斐波那契数列的升级版当前途径状态量是除前一元素先前途径状态量的和 所以dp最优问题是实质上是在dp决策问题上施加额外条件形成的因为决策的形成带动形成了解的结构所以最优问题的解也是可以进行状态转移的。
