买卖股票1

买卖股票2

买卖股票 - 图1

回溯

  1. namespace l122_1 {
  2.     function maxProfit(prices: number[]): number {
  3.         // dfs的参数往往是动态规划的状态
  4.         const memo: number[][] = new Array(prices.length)
  5.             .fill(0)
  6.             .map((item) => new Array(2).fill(-1)); //
  7.         function dfs(state: boolean, i: number): number {
  8.             /*
  9.              * profit 表示当前状态下， [i...end]*还能*获利多少
  10.              * state 表示当前持有还是未买入。 只要买入state就是持有状态
  11.              * j:何时买入
  12.              */
  14.             // base case
  15.             if (i === prices.length) {
  16.                 return 0;
  17.             }
  19.             // make choices
  20.             if (state) {
  21.                 // 持有状态 卖出或继续持有
  22.                 if (memo[i][1] !== -1) {
  23.                     return memo[i][1];
  24.                 }
  25.                 let result = Math.max(
  26.                     prices[i] + dfs(false, i + 1),
  27.                     dfs(true, i + 1)
  28.                 );
  29.                 memo[i][1] = result;
  30.                 return result;
  31.             } else {
  32.                 // 非持有状态 买入或者继续非持有
  33.                 if (memo[i][0] !== -1) {
  34.                     return memo[i][0];
  35.                 }
  36.                 let result = Math.max(
  37.                     -prices[i] + dfs(true, i + 1),
  38.                     dfs(false, i + 1)
  39.                 );
  40.                 memo[i][0] = result;
  41.                 return result;
  42.             }
  43.         }
  44.         let result = dfs(false, 0);
  45.         console.table(memo);
  47.         return result;
  48.     }
  49.     maxProfit([7, 1, 5, 3, 6, 4]);
  50. }

动态规划

  1. namespace l122_2 {
  2.     function maxProfit(prices: number[]): number {
  3.         /*
  4.          * dfs的参数往往是动态规划的状态， 但是含义可能不一样， 回溯一般是自顶向下， 反之亦反。
  5.          * 状态/局面：dp[i][state]  表示state下，前i天最大
  6.          * base case dp[0][买入] = -nums[0] dp[0][卖出] = X
  7.          *
  8.          * */
  10.         const dp: number[][] = new Array(prices.length)
  11.             .fill(0)
  12.             .map((item) => new Array(2).fill(Number.NEGATIVE_INFINITY));
  13.         dp[0][0] = 0;
  14.         dp[0][1] = -prices[0];
  15.         for (let i = 1; i < prices.length; i++) {
  16.             // 持有状态
  17.             /*
  18.              当前是持有状态， 如果是i买入， 那么前面必须是非持有状态；如果不是i买入， 说明前面是持有状态
  20.              */
  21.             dp[i][1] = Math.max(dp[i - 1][1], -prices[i] + dp[i - 1][0]);
  23.             // 非持有状态
  24.             dp[i][0] = Math.max(dp[i - 1][0], prices[i] + dp[i - 1][1]);
  25.         }
  26.         console.table(dp);
  27.         // 最高利润肯定非持有状态取得
  28.         return dp[prices.length - 1][0] > 0 ? dp[prices.length - 1][0] : 0;
  29.     }
  30.     maxProfit([1, 2, 3, 4, 5]);
  31. }

总结

  • 画出状态转移图
  • 由dfs获得灵感， dfs参数和dp状态往往是一样的， 不过其含义可能不同
    • dfs自顶向下
    • dp自底向上