中国门户网站排行,html5 网站开发 适配,扬中网站设计公司,wordpress 主题 google有想要了解打家劫舍初级问题的#xff0c;可以点击下面链接查看#xff01; 每日一练#xff1a;“打家劫舍“#xff08;House Robber#xff09;问题 I
1. 问题 假设有房屋形成一个环形#xff0c;即第一个房屋和最后一个房屋也相邻#xff0c;每个房屋里都存放着一定…
有想要了解打家劫舍初级问题的可以点击下面链接查看 每日一练“打家劫舍“House Robber问题 I
1. 问题 假设有房屋形成一个环形即第一个房屋和最后一个房屋也相邻每个房屋里都存放着一定数量的财宝。相邻的房屋装有相互连通的防盗系统如果两个相邻的房屋在同一晚上被小偷闯入系统会自动报警。 求解的问题是小偷在不触发警报的情况下一晚上最多能偷到多少财宝。
2. 解题思路状态转移方程
2.1 状态转移方程 状态转移方程是系统动力学中描述系统状态随时间演变的数学方程。这种方程通常用来表示系统的状态如何从一个时间点转移到下一个时间点。在控制理论、物理系统建模、经济学等领域状态转移方程是非常常见且重要的概念。 一般而言状态转移方程可以用如下的形式表示 ·x(t)是系统在时间t的状态向量。 ·u(t)是在时间t的输入向量。 ·A是状态转移矩阵描述系统状态如何随时间演变。 ·B是输入矩阵描述输入如何影响状态的演变。 这个方程表示系统在下一个时间点的状态x(t1)是当前状态x(t)通过矩阵A的变换加上输入u(t)通过矩阵B的变换得到的。 在一些应用中状态转移方程也可能包含时间的影响、随机扰动等因素具体形式可能会更加复杂。
2.2 解题思路 为了应用状态转移方程解决这个问题可以将问题抽象成一个动态规划问题其中状态表示小偷在每个房屋处的状态。假设有n个房屋用f()表示小偷在第个房屋时能够获得的最大财物价值。状态转移方程可以表示为: f(i)是在第个房屋时能够获得的最大财物价值价值[i是第我个房屋中的财物价值。 f(i-1)表示小偷选择不盗窃当前房屋所以能够获得的最大财物价值与前一个房屋的最大财物价值相同。 F(i-2)value[i]表示小偷选择盗窃当前房屋所以能够获得的最大财物价值为前两个房屋的最大财物价值加上当前房屋的财物价值。 这个状态转移方程反映了一个典型的动态规划问题通过递推求解可以找到小偷在整个房屋序列中能够获得的最大财物价值。这个问题的动态规划解法避免了重复计算提高了效率
3. 代码设计思路 当处理环形房屋的打家劫舍问题时我们可以利用动态规划的思想定义一个动态规划数组 dp其中 dp[i] 表示前 i 个房屋中小偷能够偷到的最大财宝数量。然后可以利用状态转移方程来更新dp 数组。 在这个问题中有两种情况需要考虑 1小偷偷第一个房屋不偷最后一个房屋这意味着小偷只能在第二个房屋到最后一个房屋中选择偷窃。这个时候状态转移方程为 2小偷不偷第一个房屋偷最后一个房屋这意味着小偷只能在第一个房屋到倒数第二个房屋中选择偷窃。这个时候状态转移方程为
3. 代码实现
def rob(nums):# 如果输入为空列表则返回0表示没有房屋可以抢劫if not nums:return 0# 定义rob_range函数用于计算在指定范围内的房屋中能够抢到的最大金额def rob_range(start, end):prev, curr 0, 0# 遍历指定范围内的房屋for i in range(start, end 1):# 记录当前位置的最大值即当前位置的最大金额temp curr# 更新当前位置的最大值考虑是否抢劫当前房屋curr max(prev nums[i], curr)# 更新前一个位置的最大值为下一次迭代做准备prev temp# 返回指定范围内的最大金额return curr# 返回不抢劫第一间房和不抢劫最后一间房的两种情况的最大值return max(rob_range(0, len(nums) - 2), rob_range(1, len(nums) - 1))# 示例
nums [2, 3, 2, 5, 7]
result rob(nums)
print(result)1rob函数是主函数接受一个代表每个房屋可抢劫金额的列表nums。 2在函数开头检查nums是否为空如果为空则返回0因为没有房屋可以抢劫。 3rob_range函数是用于计算在指定范围内的房屋中能够抢到的最大金额的辅助函数。 4在rob_range函数中使用动态规划的思想遍历指定范围内的房屋计算在每个位置能够抢到的最大金额。 5主函数中调用两次rob_range函数分别表示不抢劫第一间房和不抢劫最后一间房的两种情况。 最终返回两种情况的最大值即能够在不触发警报的情况下抢到的最大金额。
4. 动态规划算法 通常用于求解具有某种最优性质的问题。 在这类问题中可能会有许多可行解。每一个解都对应于一个值希望找到具有最优值的解。 动态规划算法与分治法类似其基本思想也是将待求解问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解。与分治法不同的是适合于用动态规划求解的问题经分解得到子问题往往不是互相独立的。若用分治法来解这类问题则分解得到的子问题数目太多有些子问题被重复计算了很多次。 如果我们能够保存已解决的子问题的答案而在需要时再找出已求得的答案这样就可以避免大量的重复计算节省时间。 可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到只要它被计算过就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样但它们具有相同的填表格式。
5. 动态规划术语 阶段把所给求解问题的过程恰当地分成若干个相互联系的阶段以便于求解过程不同阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下阶段变量是离散的用k表示。此外也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策且在任意两个不同的时刻之间允许有无穷多个决策时阶段变量就是连续的 。 状态状态表示每个阶段开始面临的自然状况或客观条件它不以人们的主观意志为转移也称为不可控因素。在上面的例子中状态就是某阶段的出发位置它既是该阶段某路的起点同时又是前一阶段某支路的终点。 无后效性我们要求状态具有下面的性质如果给定某一阶段的状态则在这一阶段以后过程的发展不受这阶段以前各段状态的影响所有各阶段都确定时整个过程也就确定了。换句话说过程的每一次实现可以用一个状态序列表示在前面的例子中每阶段的状态是该线路的始点确定了这些点的序列整个线路也就完全确定。从某一阶段以后的线路开始当这段的始点给定时不受以前线路所通过的点的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展这个性质称为无后效性。 决策一个阶段的状态给定以后从该状态演变到下一阶段某个状态的一种选择行动称为决策。在最优控制中也称为控制。在许多问题中决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量因状态满足无后效性故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史 [6] 。 决策变量的范围称为允许决策集合 。 策略由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程可供选取的策略有一定的范围限制这个范围称为允许策略集合 。 允许策略集合中达到最优效果的策略称为最优策略。 给定k阶段状态变量x(k)的值后如果这一阶段的决策变量一经确定第k1阶段的状态变量x(k1)也就完全确定即x(k1)的值随x(k)和第k阶段的决策u(k)的值变化而变化那么可以把这一关系看成(x(k)u(k))与x(k1)确定的对应关系用x(k1)Tk(x(k),u(k))表示。这是从k阶段到k1阶段的状态转移规律称为状态转移方程 。 最优化原理作为整个过程的最优策略它满足相对前面决策所形成的状态而言余下的子策略必然构成“最优子策略”。 最优性原理实际上是要求问题的最优策略的子策略也是最优。
相关文章：
