思路 多维的动态规划，属于背包类问题，只是穷举多了个背包。 strs里的每个元素就是物品，m为装1的背包数量，n为装0的背包数量，开始DP套路： 定义状态：dp[i][m][n]表示0-i个物品，m个装1的背包，n个装0的背包可以装下多少个物品 状态转移方程：dp[i][m][n]=max(dp[i-1][m][n],dp[i-1][m-i1][n…

一、思路 选择是有上限的，10张彩票让你买，你最多也只能买10张。 为什么在乎这个选择的数量呢？因为我将题目中的无限次可交易次数作为了选择：选一次交易次数，选两次交易次数。然后取最优的选择。 动态规划的精髓就是找出选择项，再去做选择 二、问题 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价…

一、思路 找出选择和状态 二、问题 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。   示例 1: 输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天…

一、思路 找出选择和状态 二、问题 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。   示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解…

一、思路 找出选择和状态 二、问题 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。   示例 …

一、思路 与前两道打家取舍相比，结合了二叉树。 选择变成了，偷当前节点，下一步就去偷孙子节点。不偷当前节点，就去偷儿子节点。两个选择一计算，看哪个状态更优。 这儿还得注意动态规划常见的重叠子问题，用哈希表来优化。 二、问题 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根&rd…

一、思路 相比打家取舍一，不能同时偷第一家和最后家。就是多了个选择，要不偷第一家，要不偷最后家。 动态规划问题就是要在题目中找出选择，得出状态。 二、问题 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相…

一、思路 这是典型的动态规划问题。要想得到最优策略，就得在每个选择时刻最出最优决策。选择产生状态，合并状态得到结果。 开始认为，求最优选择时，只计算某一个选择。导致不知道怎么得出某一个。后来发现，应该把所有选择都计算，得到多个状态，取最优的状态。 二、问题 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就…