欢迎关注本人的微信公众号AI_Engine
题目1：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 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 。
答案：
分析：打家劫舍这道题目是动态规划中的简单题，但是个人觉得还是蛮有意思的，所以今天的主题就是将一些有意思的题目做以分享，也希望大家能喜欢。打家劫舍这道题在近两年作为面试题出现的公司有百度，腾讯，谷歌，微软，网易等等，这样看来互联网公司面试的时候还是比较open的哈。这道题还是先往简单的情况分析（题目降维），即如果只有一个房屋可以打劫的时候，显然最大值就是第一个房屋内的金额。当用f(n)表示从前面n个房屋中获取的最大金额，则f(1) = nums[0]。同理f(2) = max(nums[0], nums[1])。当房屋变成3个的时候情况发生了变化，就是小偷可能要思考一下我偷不偷第3个房屋的钱，如果偷了，那么第二个房屋的钱我就不能偷。也就是说他为了争取利益最大化，就要在只偷第2个房屋的钱和偷1和3房屋的钱之间进行比较大小，这样得出的答案就是在有3个房屋的情况下能获得的最大金额。现在房屋变成了4个，小偷现在又要合计了，如果我偷第4个房屋的钱，那第三个房屋的钱我就不能碰，这样我就需要将只有2个房屋情况下的最大收益与第4个房屋的收益进行求和，然后与我不偷第4个房屋情况下的收益（就是只有3个房屋可偷的情况下的收益）进行比较大小。经过这样的迭代，就会将从1到n个房屋的情况下的最大收益记录下来，然后返回出记录表里的最后一个元素就是最大值了。而这个记录表就是我们维护的dp矩阵，状态转移方程就是f(n) = max(f(n-2)+nums[n], f(n-1))。
题目2：假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。
示例 1:
输入: [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。最少花费: 2 + 5 + 3 = 10。
答案：
分析：这道题目同样也是动态规划中的简单题，在近两年作为面试题出现的公司有领英等。虽然这道题并不是很火，难度也是简单题，但是个人觉得对入门动态规划还是有帮助的。一开始有的同学的思路是把每行的最小元素求和就ok了，那么这样的状态转移方程就是min_cost[n] = min(costs[n][0], costs[n][1], costs[n][2]) + min_costs[n-1]。但是这种思路是错误的，因为对于当前的颜色选择，我们要知道上一次粉刷的是color，才能确定当前状态的color。而且我们要知道上一个状态的三种color的各自的cost，才能确定当前用哪个color的cost最小。什么意思呢？我举个例子，假设costs的数组是这样[10, 15, 30], [1, 10, 20]，然后我们理所当然的选择当前行的最小元素进行求和，这样max_value = 10+10=20（第二行不选1的原因是在第1行与第2行不能选择同一个索引值的元素），但是其实有更便宜的选择：15+1=16。之所以会发生这种情况是我们在选择第二行元素的时候已经把第一行的元素选好了，所以不要着急做出选择。换句话说，如果先让你选择第二行的元素，我们是不是要针对第二行的所有元素并结合第一行的元素进行分析比较。按照这个思路，我们的状态转移方程应该就是dp[i][j] = costs[i][j] + min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]), dp就是我们维护的动态规划矩阵，其中每个元素都是选择当前color的最少成本。代码实现可以将状态转移方程表达出来，但是这样更方便读者们的理解，而且执行效率非常高，如图所示：
今天的分享就做到这了，动态规划其实还是要刷刷题的，思路形成后就会有潜意识了。希望各位读者在评论区多提宝贵意见，多多指正，先谢谢大家了！
网友评论