怎样做自己的销售网站,沧州全网推网络科技有限公司,wordpress调用置顶文章,企业建设网页LC121买卖股票的最佳时机#xff08;未掌握#xff09;
暴力#xff1a;双层循环寻找最优间距#xff0c;每一次都确定一个起点#xff0c;遍历剩余节点当作终点 贪心#xff1a;取最左最小值#xff0c;不断遍历那么得到的差值最最大值就是最大利润。 动态规划 dp数组…LC121买卖股票的最佳时机未掌握
暴力双层循环寻找最优间距每一次都确定一个起点遍历剩余节点当作终点 贪心取最左最小值不断遍历那么得到的差值最最大值就是最大利润。 动态规划 dp数组的含义 dp[i][0] 表示第i天持有股票所得最多现金dp[i][1] 表示第i天不持有股票所得最多现金 递归式的推导 dp[i][0]第i-1天持有和第i天买入的最多现金Math.max(dp[i-1][0],-price[i])因为本金是0且只能操作一次所以第i天买入的最多现金为-price[i]dp[i][1]第i-1天不持有和第i天卖出的最多现金Math.max(dp[i-1][1],dp[i-1][0]price[i]) 代码
LC122买卖股票的最佳时机II
与LC121买卖股票的最佳时机不同的是LC121只能买入卖出一次而LC122可以买入卖出多次因此第i天买入的最多现金为dp[i-1][1]-price[i]代码
LC123买卖股票的最佳时机III(未掌握)
LC123与LC122不同的是LC123只能允许买入两次而LC122可以买入无数次因此使用5个状态来记录五种情况 0无操作这个状态是用来帮助统计第一次持有股票的情况的1第一次持有股票2第一次不持有股票3第二次持有股票4第二次不持有股票 递归公式 dp[i][0] dp[i-1][0]dp[i][1] 第i-1天第一次就持有股票和第i-1天不持有股票第i天买入 Math.max(dp[i-1][1], dp[i-1][0]-price[i])dp[i][2] 第i-1天第一次就不持有股票和第i-1天持有股票第i天卖出 Math.max(dp[i-1][2], dp[i-1][1]price[i])dp[i][3] 第i-1天第二次就持有股票和第i-1天第一次不持有股票第i天买入第二次 Math.max(dp[i-1][3], dp[i-1][2]price[i])dp[i][4] 第i-1天第二次就不持有股票和第i-1天持有第二次股票第i天卖出 Math.max(dp[i-1][4], dp[i-1][3]price[i]) 初始化 第0天没有操作这个最容易想到就是0即dp[0][0] 0;第0天做第一次买入的操作dp[0][1] -prices[0];第0天做第一次卖出的操作可以理解为当天买入当天卖出所以dp[0][2] 0;第0天第二次买入操作可以理解为第二次买入依赖于第一次卖出的状态其实相当于第0天第一次买入了第一次卖出了然后再买入一次第二次买入初始化为dp[0][3] -prices[0];同理第二次卖出初始化dp[0][4] 0; 代码
LC188买卖股票的最佳时机IV
LC123是买入两次LC188是买入k次因此j的值应该设置为2k1种代表2k1种情况根据规律可知 初始化的时候dp[0][j]只要j为1、3、5…2*k-1时值为-price[0]同理j两两一组表示j次买入股票和卖出股票的最多金额 代码
