递归

  • 状态: 怎么描述问题, 当前是持有/未持有状态下， 能获得的最大利润
  • 缩小问题规模： 到哪里去/从哪里来

  • 当前状态下，如何做选择才能获利最大？ 到哪里去 ```typescript export function maxProfit(prices: number[]): number { // [day…最后一天]最大利润

    const cache: number[][] = new Array(prices.length) .fill(0) .map(() => new Array(2).fill(-1));

    function backtrack(day: number, state: boolean): number { / state=true表示持有状态 /

    // base case if (day >= prices.length) {

    1. return 0;

    }

    if (cache[day][state ? 0 : 1] !== -1) return cache[day][state ? 0 : 1];

    if (state) {

    1. cache[day][state ? 0 : 1] = Math.max(
    2.   prices[day] + backtrack(day + 1, !state),
    3.   backtrack(day + 1, state)
    4. );

    } else {

    1. cache[day][state ? 0 : 1] = Math.max(
    2.   -prices[day] + backtrack(day + 1, !state),
    3.   backtrack(day + 1, state)
    4. );

    }

    return cache[day][state ? 0 : 1]; }

    return backtrack(0, false); }

console.log(maxProfit([7, 1, 5, 3, 6, 4]));

  1. <a name="jNmCi"></a>
  2. # 动态规划
  4. - State: 第几天，持有或者非持有状态 的最优价值
  5. - 涉及到连续不连续的问题往往需要某个方法来体现。这题目理论上是不连续的问题，但是由于将price预先处理，因此这个不连续其实并不需要考虑，
  6. - 当前状态时如何形成的，以及它的最优解 从哪里来
  8. - 不连续处理
  9. ```typescript
  10.  function maxProfit(prices: number[]): number {
  11.     // State ,  status下 第几天的最优解
  12.     const dp: number[][] = new Array(prices.length)
  13.         .fill(0)
  14.         .map(() => new Array(2).fill(-1));
  16.     // base case
  18.     dp[0][0] = 0;
  19.     dp[0][1] = -prices[0];
  21.     // make progress
  22.     for (let i = 1; i < prices.length; i++) {
  23.         // 未持有状态 该状态是前面保留的状态或是当天卖出
  24.         // 当天卖出 卖出的是那一天的
  26.         {
  27.             const days = [...Array(i).keys()].filter(
  28.                 (day) => prices[day] < prices[i]
  29.             );
  31.             const profits = days.map((day) => dp[day][1] + prices[i]);
  32.             dp[i][0] = Math.max(dp[i - 1][0], Math.max(...profits));
  33.         }
  34.         // 持有状态  该状态是前面保留的或是当天买入
  35.         {
  36.             dp[i][1] = Math.max(dp[i - 1][1], dp[i][0] - prices[i]);
  37.         }
  38.     }
  39.     console.table(dp);
  40.     return dp[prices.length - 1][0];
  41. }

  • 连续

    1. function maxProfit(prices: number[]): number {
    2.   // State ,  status下 第几天的最优解
    3.   const dp: number[][] = new Array(prices.length)
    4.       .fill(0)
    5.       .map(() => new Array(2).fill(-1));
    7.   // base case
    9.   dp[0][0] = 0;
    10.   dp[0][1] = -prices[0];
    12.   // make progress
    13.   for (let i = 1; i < prices.length; i++) {
    14.       // 未持有状态 该状态是前面保留的状态或是当天卖出
    15.       // 当天卖出 卖出的是那一天的
    17.       {
    18.           dp[i][0] = Math.max(dp[i - 1][0],  dp[i-1][1] + prices[i]);
    19.       }
    21.       // 持有状态  该状态是前面保留的或是当天买入
    22.       {
    23.           dp[i][1] = Math.max(dp[i - 1][1], dp[i][0] - prices[i]);
    24.       }
    25.   }
    26.   return dp[prices.length - 1][0];
    27. }