哪个设计网站赚钱,免费项目管理软件app,开源微信小程序商城,滨州网站建设公司电话今天来看看动态规划的打家劫舍和买卖股票的问题。
上题目#xff01;#xff01;#xff01;#xff01;
题目#xff1a;打家劫舍 198. 打家劫舍 - 力扣#xff08;LeetCode#xff09; 你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金…今天来看看动态规划的打家劫舍和买卖股票的问题。
上题目
题目打家劫舍 198. 打家劫舍 - 力扣LeetCode 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
题目分析 对于每一房间其实只有两种状态偷或不偷而且这个状态也取决于之前偷没偷。五部曲分析。
dp[i]:小偷到第i间放的最大金额
i的两种状态偷不偷
不偷dp[i]dp[i-1]
偷dp[i]dp[i-2]
dp[0]nums[0] dp[1]max(nums[0],nums[1])
public class Solution {public int Rob(int[] nums) {if(nums.Length0) return 0;if(nums.Length1) return nums[0];int[] dpnew int[nums.Length];dp[0]nums[0];dp[1]Math.Max(nums[0],nums[1]);for(int i2;inums.Length;i){dp[i]Math.Max(dp[i-2]nums[i],dp[i-1]);}return dp[nums.Length-1];}
} 题目打家劫舍 2 213. 打家劫舍 II - 力扣LeetCode 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
题目分析 房子围城一圈那么对于首尾的房子而言我们只能偷一个其他的房间呢则尽量偷。本质上就和上一题一样了无非是偷的时候划分一下区间即可其他部分完全一样。
public class Solution {public int Rob(int[] nums) {if(nums.Length0) return 0;if(nums.Length1) return nums[0];int res1RobRange(nums,0,nums.Length-2);int res2RobRange(nums,1,nums.Length-1);return Math.Max(res1,res2);}public int RobRange(int[] nums,int start,int end){if (end start) return nums[start];int[] dpnew int[nums.Length];dp[start]nums[start];dp[start1]Math.Max(nums[start],nums[start1]);for(int istart2;iend;i){dp[i]Math.Max(dp[i-2]nums[i],dp[i-1]);}return dp[end];}
}
题目打家劫舍 III 337. 打家劫舍 III - 力扣LeetCode 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为 root 。
除了 root 之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 小偷能够盗取的最高金额 。
题目分析 房子的排列变成了树形结构那么不触发警报意味着如果我们偷了一个结点那么他的两个子节点都不能偷。 其实结点的状态任然是两种偷或者不偷。但是我们要偷取的金额最大一定要考虑不偷这个的情况下他的左右子节点偷不偷呢。所以需要将左右孩子的偷不偷的最大金额返回给父节点那么对于这个树的遍历只能使用后序遍历的方式。
public class Solution {public int Rob(TreeNode root) {int[] resRobTrue(root);return Math.Max(res[1],res[0]);}public int[] RobTrue(TreeNode root){if(rootnull) return new int[2]{0,0};int[] leftDpRobTrue(root.left);int[] rightDpRobTrue(root.right);//下标为0记录不偷该节点所得到的的最大金钱下标为1记录偷该节点所得到的的最大金钱。int res1root.valleftDp[0]rightDp[0];//偷这个结点加上不偷左右孩子的最大值int res2Math.Max(leftDp[0],leftDp[1])Math.Max(rightDp[0],rightDp[1]);//不偷这个结点就考虑左右孩子要不要偷return new int[]{res2,res1};}
}
题目买卖股票的最佳时机 121. 买卖股票的最佳时机 - 力扣LeetCode 给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
题目分析 这一题可以用暴力和贪心的方法解决。
暴力依次枚举股票价格并且找出最大差值作为结果即可。
贪心的想法很自然就是取最左最小值取最右最大值那么得到的差值就是最大利润。
两者差不多。
public class Solution {public int MaxProfit(int[] prices) {int minint.MaxValue;int res0;for(int i0;iprices.Length;i){minMath.Min(prices[i],min);resMath.Max(res,prices[i]-min);}return res;}
}
动态规划 考虑股票的状态其实就只有持有和不持有两种状态。注意这里的持有和不持有并不是买入卖出的意思。来看看dp数组的解释。
dp[i][0]:在第i天这支股票在我手上持有的最大金额利润
dp[i][1]:在第i天这支股票不在我手上持有的最大金额利润
注意两个的区别因为这个持有和不持有他需要考虑前一天的状态也就是说在这一天之前这个股票我可能已经买入或者卖出了。这个很重要。
递推公式
持有股票1.在这一天之前我就持有了 2之前我没有但是今天买入后持有了
1.dp[i-1][0] 2.-price[i] dp[i][0]max(dp[i-1][0],-price[i]) 不持有股票1.在这一天之前我就没有了 2之前我有但是今天卖了后就没有了
1.dp[i-1][1] 2.dp[i-1][0]price[i] dp[i][0]max(dp[i-1][1] ,dp[i-1][0]price[i])
初始化就很好理解了那么来看看代码
public class Solution {public int MaxProfit(int[] prices) {int[,] dpnew int[prices.Length,2];dp[0,0]-prices[0];//持有这个股票dp[0,1]0;//不持有这个股票for(int i1;iprices.Length;i){dp[i,0]Math.Max(-prices[i],dp[i-1,0]);dp[i,1]Math.Max(dp[i-1,0]prices[i],dp[i-1,1]);}return Math.Max(dp[prices.Length-1,0],dp[prices.Length-1,1]);}
} 题目买卖股票的最佳时机II 122. 买卖股票的最佳时机 II - 力扣LeetCode 给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。
题目分析 注意和上一题的区别题目中的每一天意味着我可以多次买入卖出。但是上一题我只能操作一次。 这里的dp的含义和上一题一样的区别是dp的递推公式。
递推公式
持有股票1.在这一天之前我就持有了 2(可能我已经卖出过了)之前我没有但是今天买入后持有了
1.dp[i-1][0] 2.dp[i-1][1]-price[i]上一天是不持有的状态 dp[i][0]max(dp[i-1][0],dp[i-1][1]-price[i])
不持有股票1.在这一天之前我就没有了 2之前我有但是今天卖了后就没有了
1.dp[i-1][1] 2.dp[i-1][0]price[i] dp[i][0]max(dp[i-1][1] ,dp[i-1][0]price[i])
public class Solution {public int MaxProfit(int[] prices) {int[,] dpnew int[prices.Length,2];dp[0,0]-prices[0];//持有这个股票dp[0,1]0;//不持有这个股票for(int i1;iprices.Length;i){dp[i,0]Math.Max(dp[i-1,1]-prices[i],dp[i-1,0]);dp[i,1]Math.Max(dp[i-1,0]prices[i],dp[i-1,1]);}return Math.Max(dp[prices.Length-1,0],dp[prices.Length-1,1]);}
} 主要区别在于持有股票是需要考虑之前是否有卖出过这一点在下面的题中很重要
题目买卖股票的最佳时机III 123. 买卖股票的最佳时机 III - 力扣LeetCode 给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 题目分析 会看前面两题第一题要求只能买入卖出1次第二题能买入卖出无数次。而这一题最多两次和上面两题一样看看股票在第i天可能出现的状态。
第一次买入
第一次卖出
第二次买入
第二次卖出
那么dp数组的含义就很好理解了。
来看看递推公式本质上和上面的题是一样的无非就是买入卖出的时候需要考虑之前的状态这一点和第二题一样。
达到dp[i][1]状态有两个具体操作
操作一第i天买入股票了那么dp[i][1] dp[i-1][0] - prices[i]操作二第i天没有操作而是沿用前一天买入的状态即dp[i][1] dp[i - 1][1]
那么dp[i][1]究竟选 dp[i-1][0] - prices[i]还是dp[i - 1][1]呢
一定是选最大的所以 dp[i][1] max(dp[i-1][0] - prices[i], dp[i - 1][1]);
同理dp[i][2]也有两个操作
操作一第i天卖出股票了那么dp[i][2] dp[i - 1][1] prices[i]操作二第i天没有操作沿用前一天卖出股票的状态即dp[i][2] dp[i - 1][2]
所以dp[i][2] max(dp[i - 1][1] prices[i], dp[i - 1][2])
同理可推出剩下状态部分
dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i]);
对于初始化而言需要注意的是你可以在一天内多次买入卖出因为price的长度可以为1。
public class Solution {public int MaxProfit(int[] prices) {int[,] dpnew int[prices.Length,5];dp[0,0]0;//0,不操作dp[0,1]-prices[0];//1,第一次持有dp[0,2]0;//2,第一次不持有dp[0,3]-prices[0];//3,第二次持有dp[0,4]0;//4,第二次不持有for(int i1;iprices.Length;i){dp[i,1]Math.Max(dp[i-1,1],-prices[i]);dp[i,2]Math.Max(dp[i-1,1]prices[i],dp[i-1,2]);dp[i,3]Math.Max(dp[i-1,3],dp[i,2]-prices[i]);dp[i,4]Math.Max(dp[i-1,4],dp[i-1,3]prices[i]);}return Math.Max(dp[prices.Length-1,4],dp[prices.Length-1,2]);}
} 对于更详细的解析与其他语言的代码块可以去代码随想录上查看。
代码随想录 (programmercarl.com)
已刷题目110
