• 和买卖股票2高度类似

      1. function maxProfit(prices: number[], fee: number): number {
      2.   const cache: number[][] = Array(prices.length)
      3.       .fill(0)
      4.       .map(() => [NaN, NaN]);
      6.   function backtrack(day: number, status: number): number {
      7.       // base case
      8.       if (day >= prices.length) {
      9.           return 0;
      10.       }
      12.       if (!isNaN(cache[day][status])) {
      13.           return cache[day][status];
      14.       }
      15.       if (status === 0) {
      16.           // 未持有
      17.           cache[day][status] = Math.max(
      18.               backtrack(day + 1, status),
      19.               -prices[day] + backtrack(day + 1, 1)
      20.           );
      21.       } else {
      22.           // 持有
      23.           cache[day][status] = Math.max(
      24.               backtrack(day + 1, status),
      25.               prices[day] - fee + backtrack(day + 1, 0)
      26.           );
      27.       }
      28.       return cache[day][status];
      29.       // make progress
      30.   }
      32.   return backtrack(0, 0);
      33. }