乐趣区

leetcode123188股票买卖题-模板DFS解法

jiezi


这两题的共同点就是有交易次数的限制，也就是说有两个状态在变化，即：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]
};
退出移动版