标签: 动态规划

7 篇文章

LeetCode188. 买卖股票的最佳时机IV
一、思路 选择是有上限的,10张彩票让你买,你最多也只能买10张。 为什么在乎这个选择的数量呢?因为我将题目中的无限次可交易次数作为了选择:选一次交易次数,选两次交易次数。然后取最优的选择。 动态规划的精髓就是找出选择项,再去做选择 二、问题 给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价…
LeetCode123. 买卖股票的最佳时机III
一、思路 找出选择和状态 二、问题 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。   示例 1: 输入:prices = [3,3,5,0,0,3,1,4] 输出:6 解释:在第 4 天…
LeetCode122. 买卖股票的最佳时机II
一、思路 找出选择和状态 二、问题 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。   示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解…
LeetCode121. 买卖股票的最佳时机
一、思路 找出选择和状态 二、问题 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。   示例 …
LeetCode337. 打家劫舍III
一、思路 与前两道打家取舍相比,结合了二叉树。 选择变成了,偷当前节点,下一步就去偷孙子节点。不偷当前节点,就去偷儿子节点。两个选择一计算,看哪个状态更优。 这儿还得注意动态规划常见的重叠子问题,用哈希表来优化。 二、问题 在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根&rd…
LeetCode213. 打家劫舍II
一、思路 相比打家取舍一,不能同时偷第一家和最后家。就是多了个选择,要不偷第一家,要不偷最后家。 动态规划问题就是要在题目中找出选择,得出状态。 二、问题 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相…
LeetCode198. 打家劫舍
一、思路 这是典型的动态规划问题。要想得到最优策略,就得在每个选择时刻最出最优决策。选择产生状态,合并状态得到结果。 开始认为,求最优选择时,只计算某一个选择。导致不知道怎么得出某一个。后来发现,应该把所有选择都计算,得到多个状态,取最优的状态。 二、问题 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就…