递归

  • 首先描述出问题

    第day天，持有or非持有的状态，已经交易times的情况下能获利多少

    1. function maxProfit(prices: number[]): number {
    2.   const cache: number[][][] = new Array(prices.length).fill(0).map(() => [
    3.       [-1, -1],
    4.       [-1, -1],
    5.   ]);
    6.   function backtrack(day: number, status: number, times: number): number {
    7.       // base case
    8.       if (day >= prices.length || times >= 2) {
    9.           return 0;
    10.       }
    12.       if (cache[day][status][times] !== -1) {
    13.           return cache[day][status][times];
    14.       }
    15.       if (status === 0) {
    16.           // make progress  到哪里去， 去哪儿
    17.           // status 未持有
    18.           cache[day][status][times] = Math.max(
    19.               -prices[day] + backtrack(day + 1, (status + 1) % 2, times),
    20.               backtrack(day + 1, status, times)
    21.           );
    22.       } else {
    23.           // 持有
    24.           cache[day][status][times] = Math.max(
    25.               prices[day] + backtrack(day + 1, (status + 1) % 2, times + 1),
    26.               backtrack(day + 1, status, times)
    27.           );
    28.       }
    30.       return cache[day][status][times];
    31.   }
    33.   return backtrack(0, 0, 0);
    34. }

    动态规划

    1. function maxProfit(prices: number[]): number {
    2.   const dp: number[][][] = new Array(prices.length).fill(0).map(() => [
    3.       [0, 0, 0],
    4.       [0, 0, 0],
    5.   ]);
    6.   let n = prices.length - 1;
    7.   // base case
    9.   dp[0][0][0] = 0;
    10.   dp[0][0][1] = Number.NEGATIVE_INFINITY;
    11.   dp[0][0][2] = Number.NEGATIVE_INFINITY;
    13.   dp[0][1][0] = -prices[0];
    14.   dp[0][1][1] = Number.NEGATIVE_INFINITY;
    15.   dp[0][1][2] = Number.NEGATIVE_INFINITY;
    17.   // make progress
    18.   for (let i = 1; i < prices.length; i++) {
    19.       // 未持有状态 从哪里来
    20.       {
    21.           dp[i][0][0] = 0;
    22.           dp[i][0][1] = Math.max(
    23.               dp[i - 1][1][0] + prices[i],
    24.               dp[i - 1][0][1]
    25.           );
    26.           dp[i][0][2] = Math.max(
    27.               dp[i - 1][1][1] + prices[i],
    28.               dp[i - 1][0][2]
    29.           );
    30.       }
    32.       // 持有状态 从哪里来 前面买入或者当前买入
    33.       {
    34.           dp[i][1][0] = Math.max(
    35.               dp[i - 1][0][0] - prices[i],
    36.               dp[i - 1][1][0]
    37.           );
    38.           dp[i][1][1] = Math.max(
    39.               dp[i - 1][0][1] - prices[i],
    40.               dp[i - 1][1][1]
    41.           );
    42.           // 已经交易两次还持有，所以不可能
    43.           dp[i][1][2] = Number.NEGATIVE_INFINITY;
    44.       }
    45.   }
    46.   console.table(dp);
    48.   return Math.max(...dp[n][0]);
    49. }