这两题的共同点就是有交易次数的限制，也就是说有两个状态在变化，即：i（当前日期即数组的索引）和k。
这里dfs的状态找到了，即dfs函数的参数：function dfs (i,k){}
实际上这里的dfs(i,k)就相当于使用动态规划的dp数组dp[i][k] 。
每一个 dfs(i,k) 内部都有两个状态，即：拥有股票和不拥有股票。
即function dfs (i,k){return [没有股票的钱，有股票的钱]}
当前 dfs(i,k) 拥有股票的值为：dfs(i-1,k)（即前一天）拥有股票状态值与dfs(i-1,k-1)不拥有股票的状态值 - prices[i]，两者中的最优值。
当前 dfs(i,k)不拥有股票的值为：dfs(i-1,k)不拥有股票状态值与dfs(i-1,k)拥有股票状态值 + prices[i]，两者中的最优值。
最后要求的结果就是：最后一天 交易了 k（或2） 次 并且不拥有股票的情况
下面是 123. 买卖股票的最佳时机 III的代码
/** * @param {number[]} prices * @return {number} */var maxProfit = function(prices) { // 股票类题模板 dfs 解法 // 可使用备忘录优化 或直接改写为 dp function dfs(i,k){ // 临界值 if(i < 0 || k === 0) return [0,Number.MIN_SAFE_INTEGER] // 当前 i k 的情况下， // 1.不拥有股票的情况： // 前一天没有股票和前一天有股票但是今天卖出 两者中的最优值 // 2.拥有股票的情况： // 前一天有股票和前一天没有股票并且只交易了k-1次（因为会在前一天没有股票的情况下进行买入交易） // 两者中的最优值 const status_0 = Math.max(dfs(i-1,k)[0],dfs(i-1,k)[1]+prices[i]) const status_1 = Math.max(dfs(i-1,k)[1],dfs(i-1,k-1)[0]-prices[i]) return [status_0,status_1] } 最后的结果为 最后一天 交易了 2 次 并且不拥有股票的情况 return dfs(prices.length-1,2)[0]---------------------分割线----------------------- // 下面使用 dp 优化的模板 const len = prices.length, dp = new Array(len) for(let i = 0; i<len; i++){ dp[i] = new Array(3) dp[i][0] = [0,Number.MIN_SAFE_INTEGER] } dp[-1] = new Array(3) dp[-1].fill([0,Number.MIN_SAFE_INTEGER]) for(let i = 0; i<len; i++){ for(let j = 1; j<=2; j++){ const status_0 = Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]) const status_1 = Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]) dp[i][j] = [status_0,status_1] } } return dp[len-1][2][0]}; 188. 买卖股票的最佳时机 IV 题解
这题跟题差不多，就是优化比上题难。容易超时。dfs几乎一模一样。
/** * @param {number} k * @param {number[]} prices * @return {number} */var maxProfit = function(k, prices) { // 股票类题模板 dfs 解法 // 可使用备忘录优化 或直接改写为 dp function dfs(i,k){ // 临界值 if(i < 0 || k === 0) return [0,Number.MIN_SAFE_INTEGER] // 当前 i k 的情况下， // 1.不拥有股票的情况： // 前一天没有股票和前一天有股票但是今天卖出 两者中的最优值 // 2.拥有股票的情况： // 前一天有股票和前一天没有股票并且只交易了k-1次（因为会在前一天没有股票的情况下进行买入交易） // 两者中的最优值 const status_0 = Math.max(dfs(i-1,k)[0],dfs(i-1,k)[1]+prices[i]) const status_1 = Math.max(dfs(i-1,k)[1],dfs(i-1,k-1)[0]-prices[i]) return [status_0,status_1] } // 最后的结果为 最后一天 交易了 k 次 并且不拥有股票的情况 return dfs(prices.length-1,k)[0]};