深圳农产品网站制作,一下成都网站建设公司排名,网络优化大师app,湖州企业网站开发公司力扣#xff08;LeetCode#xff09;是一个在线编程平台#xff0c;主要用于帮助程序员提升算法和数据结构方面的能力。以下是一些力扣上的入门题目#xff0c;以及它们的解题代码。 --点击进入刷题地址 引言#xff1a; 在算法的世界中#xff0c;动态规划#xff… 力扣LeetCode是一个在线编程平台主要用于帮助程序员提升算法和数据结构方面的能力。以下是一些力扣上的入门题目以及它们的解题代码。 --点击进入刷题地址 引言 在算法的世界中动态规划Dynamic Programming, DP是一种非常重要的思想它帮助我们解决了许多看似复杂的问题。在力扣LeetCode上DP题目的挑战性和实用性都备受赞誉。今天我们将深入探讨一道DP的经典题目“打家劫舍”。 题目描述 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金你希望偷窃得到的现金总额最大。但是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额。
示例
输入:
[1,2,3,1]
输出:
4
解释:
偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。
偷窃到的最高金额 1 3 4 。
解题思路 对于这个问题我们可以使用动态规划的方法来解决。首先我们定义一个数组dp其中dp[i]表示偷窃前i个房屋所能获得的最大金额。考虑到小偷不能偷窃相邻的房屋所以对于第i个房屋他有两种选择 如果偷窃第i个房屋那么就不能偷窃第i-1个房屋所以此时的最大金额为dp[i-2] nums[i]其中nums[i]表示第i个房屋的金额。如果不偷窃第i个房屋那么最大金额就是dp[i-1]即偷窃前i-1个房屋所能获得的最大金额。 综上所述我们可以得到状态转移方程dp[i] max(dp[i-2] nums[i], dp[i-1]) 最后我们只需要返回dp[n-1]其中n是房屋的数量即为偷窃所有房屋所能获得的最大金额。 代码实现
def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] dp [0] * len(nums) dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] max(dp[i-2] nums[i], dp[i-1]) return dp[-1] 总结 通过这道题目我们可以看到动态规划的强大之处。它能够将问题分解为子问题并利用子问题的解来构建原问题的解。在实际应用中我们可以利用动态规划的思想来解决许多具有重叠子问题和最优子结构的问题。通过不断地练习和思考我们可以更加熟练地掌握动态规划的技巧从而更好地应对各种算法挑战。
