【每日算法】动态规划六

目录

1014.最佳观光组合

121.买卖股票的最佳时机

122.买卖股票的最佳时机ii

309.最佳买卖股票时机含冷冻期

难度[中等]

已知：f(i,j)=values[i] + i + values[j] - j (i小于j)，求f(i,j)最大

f(i,j)最大，在j之前的values[i]+i 最大，与当前的values[j]-j 最大值

定义两个数组dp_plus[j]为j之前最大值,dp[j]要求的结果

难度[简单]

定义f(x)为第x天所能获取的最大利润，最大利润有买入时的价格，和当天价格的差值

定义买入的价格为ru，所有f(x)=max(prices[x]-ru,f(x-1))

ru的值为min(ru,prices[x])

第一种:贪心算法

贪心算法只求局部最优解，再把每个局部最优的

遇到比前一个价格高的就卖出，累计求和

第二种: 动态规划

因为可以频繁买入卖出，所以针对每一天的股票都有可能持有或不持有，所以定义两个状态，f(i,(0|1)),表示持有当天或不持有时获取的最大利润

利润最大时为最后一天时把手里的股票给卖出去<code>dp[-1][0]</code>

f(i)为第i天的最大利润，因为可以多次买卖，所以第i天有两种状态f(i,0)持有股票时的最大利润，和f(i,1)不持有股票时的最大利润；又因为在卖出的第二天是处于冷冻期的，无法进行交易，所以还需要一个状态f(i,2)处于冷冻期时的最大利润