What is Memorization Search

记忆化搜索一个模板秒杀6道股票题

121. 买卖股票的最佳时机：买入卖出一支股票

首先可以从最暴力的方法出发，再加上缓存就是记忆化搜索啦

方法一：回溯

  1. 从第0天开始到第n-1天，枚举买入或者不买入两种操作，记录能获得的最大值。
  2. 定义了三种状态state
    1. state == 0，初始状态，没有买入卖出股票
      • 当前可以不买入股票，此时能获得的价值为：dfs(index + 1, state)
      • 或者买入股票，此时能获得的价值为：dfs(index + 1, state + 1) - prices[index]
    2. state == 1，已经买入了一支股票
      • 当前可以不卖出股票，此时能获得的价值为：dfs(index + 1, state)
      • 或者卖出股票，此时能获得的价值为：dfs(index + 1, state + 1) + prices[index]
    3. state == 2，已经买入卖出一支股票，操作结束
  3. 在state == 0 和 state == 1的时候返回最大的价值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices) {
        this.prices = prices;
        return dfs(0, 0);
    }

    int[] prices;

    private int dfs(int index, int state) {
        if (index == prices.length || state == 2)
            return 0;
        if (state == 0)
            // 不操作 买入
            return Math.max(dfs(index + 1, state), dfs(index + 1, state + 1) - prices[index]);
        // 不操作 卖出
        return Math.max(dfs(index + 1, state), dfs(index + 1, state + 1) + prices[index]);
    }
}

方法二：记忆化搜索

  1. 定义dp数组，用于遍历过每种状态能获得的值，dp = new int[2][prices.length];

  2. 在return前，把当前的值记录在dp数组中

    • return dp[state][index] = Math.max(dfs(index + 1, state), dfs(index + 1, state + 1) - prices[index]);
    • return dp[state][index] = Math.max(dfs(index + 1, state), dfs(index + 1, state + 1) + prices[index]);

  3. 很多子问题可能会被多次调用，导致重复计算，这会极大地增加算法的时间复杂度。记忆化数组的作用就是将已经计算过的子问题的结果保存起来，下次遇到相同的子问题时，直接从记忆数组中取得结果，避免重复计算。

    1
    2
    if (dp[state][index] != -1)
        return dp[state][index];

  4. base case：index超过了数组长度或者卖出了股票

    1
    2
    if (index == prices.length || state == 2)
        return 0;

    代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxProfit(int[] prices) {
        this.prices = prices;
        dp = new int[2][prices.length];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    int[] prices;
    int[][] dp;

    private int dfs(int index, int state) {
        if (index == prices.length || state == 2)
            return 0;
        if (dp[state][index] != -1)
            return dp[state][index];
        if (state == 0)
            // 不操作 买入
            return dp[state][index] = Math.max(dfs(index + 1, 0), dfs(index + 1, 1) - prices[index]);
        // 不操作 卖出
        return dp[state][index] = Math.max(dfs(index + 1, 1), dfs(index + 1, 2) + prices[index]);
    }
}

接下来使用记忆化搜索解决其他5道股票问题

122. 买卖股票的最佳时机 II：可以买卖任意支股票

有两处代码需要修改

  1. 买入一只股票后，可以不操作，或者卖出，由于可以买卖任意支股票，选择卖出股票后，状态回到0

    1
    return dp[state][index] = Math.max(dfs(index + 1, 1), dfs(index + 1, 0) + prices[index]);

  2. base case：删除state == 2，这段条件，因为现在可以买卖任意支股票

    1
    2
    if (index == prices.length)
        return 0;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxProfit(int[] prices) {
        this.prices = prices;
        dp = new int[2][prices.length];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    int[] prices;
    int[][] dp;

    private int dfs(int index, int state) {
        if (index == prices.length)
            return 0;
        if (dp[state][index] != -1)
            return dp[state][index];
        if (state == 0)
            // 不操作 买入
            return dp[state][index] = Math.max(dfs(index + 1, 0), dfs(index + 1, 1) - prices[index]);
        // 不操作 卖出
        return dp[state][index] = Math.max(dfs(index + 1, 1), dfs(index + 1, 0) + prices[index]);
    }
}

123. 买卖股票的最佳时机 III：最多买卖两支股票

多定义两种state即可 ，state为偶数的时候可以选择不操作或者不买入，state为奇数的时候可以选择不操作或不卖出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int maxProfit(int[] prices) {
        this.prices = prices;
        dp = new int[4][prices.length];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    int[] prices;
    int[][] dp;

    private int dfs(int index, int state) {
        if (index == prices.length || state == 4)
            return 0;
        if (dp[state][index] != -1)
            return dp[state][index];
        if (state == 0 || state == 2)
            // 不操作 买入
            return dp[state][index] = Math.max(dfs(index + 1, state), dfs(index + 1, state + 1) - prices[index]);
        // 不操作 卖出
        else
            return dp[state][index] = Math.max(dfs(index + 1, state), dfs(index + 1, state + 1) + prices[index]);
    }
}

188. 买卖股票的最佳时机 IV：最多买卖k支股票

和123. 买卖股票的最佳时机 III：最多买卖两支股票类似，买卖一支股票我们需要开2个dp数组，买卖两支股票我们需要开4个dp数组，买卖k支股票需要开2*k个dp数组

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int maxProfit(int k, int[] prices) {
        this.prices = prices;
        this.k = k;
        dp = new int[2 * k][prices.length];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    int[] prices;
    int[][] dp;
    int k;

    private int dfs(int index, int state) {
        if (index == prices.length || state == 2 * k)
            return 0;
        if (dp[state][index] != -1)
            return dp[state][index];
        if (state % 2 == 0)
            // 不操作 买入
            return dp[state][index] = Math.max(dfs(index + 1, state), dfs(index + 1, state + 1) - prices[index]);
        // 不操作 卖出
        else
            return dp[state][index] = Math.max(dfs(index + 1, state), dfs(index + 1, state + 1) + prices[index]);
    }
}

714. 买卖股票的最佳时机含手续费

与122. 买卖股票的最佳时机 II：可以买卖任意支股票类似，在卖出的时候多 - fee就ok

1
return dp[state][index] = Math.max(dfs(index + 1, 1), dfs(index + 1, 0) + prices[index] - fee);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int maxProfit(int[] prices, int fee) {
        this.prices = prices;
        this.fee = fee;
        dp = new int[2][prices.length];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    int[] prices;
    int[][] dp;
    int fee;

    private int dfs(int index, int state) {
        if (index == prices.length)
            return 0;
        if (dp[state][index] != -1)
            return dp[state][index];
        if (state == 0)
            // 不操作 买入
            return dp[state][index] = Math.max(dfs(index + 1, 0), dfs(index + 1, 1) - prices[index]);
        // 不操作 卖出
        else
            return dp[state][index] = Math.max(dfs(index + 1, 1), dfs(index + 1, 0) + prices[index] - fee);
    }
}

309. 最佳买卖股票时机含冷冻期

与122. 买卖股票的最佳时机 II：可以买卖任意支股票类似，在卖出的时候往后走两天即可dfs(index + 2, 0)，同时base case小修

  1. base case

    1
    2
    if (index >= prices.length)
        return 0;

  2. state == 1

    1
    return dp[state][index] = Math.max(dfs(index + 1, 1), dfs(index + 2, 0) + prices[index]);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int maxProfit(int[] prices) {
        this.prices = prices;
        dp = new int[2][prices.length];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    int[] prices;
    int[][] dp;

    private int dfs(int index, int state) {
        if (index >= prices.length)
            return 0;
        if (dp[state][index] != -1)
            return dp[state][index];
        if (state == 0)
            // 不操作 买入
            return dp[state][index] = Math.max(dfs(index + 1, 0), dfs(index + 1, 1) - prices[index]);
        // 不操作 卖出
        else
            return dp[state][index] = Math.max(dfs(index + 1, 1), dfs(index + 2, 0) + prices[index]);
    }
}

最后

打个比方

  1. dp(手动挡)：需要初始化，考虑遍历顺序
  2. 记忆化搜索(自动挡)：不需要初始化，考虑遍历顺序

记忆化搜索和动态规划都是解决问题的常用方法，它们各自有一些优点和缺点。

记忆化搜索的优点：

减少重复计算：记忆化搜索通过缓存已经计算过的结果，避免了重复计算，提高了算法的效率。 简单易实现：相对于动态规划，记忆化搜索的实现通常更加简单直观，只需要在递归的基础上加上缓存即可。 记忆化搜索的缺点：

可能会占用较大的内存：记忆化搜索需要缓存所有的中间结果，如果问题规模较大，可能会占用较多的内存空间。 递归调用可能导致栈溢出：对于问题规模较大的情况，递归调用深度可能较深，可能导致栈溢出。 动态规划的优点：

自底向上的思路：动态规划通常采用自底向上的计算方式，从小规模问题开始逐步推导得到最终结果，确保所有子问题的解都被计算到。 适用于一些具有最优子结构的问题：动态规划适用于具有最优子结构的问题，即整个问题的最优解可以由子问题的最优解推导得到。 动态规划的缺点：

实现较为复杂：相对于记忆化搜索，动态规划的实现通常较为复杂，需要设计合适的状态转移方程和数组结构。 可能会占用较大的内存：类似于记忆化搜索，动态规划也需要维护一个数组来保存中间结果，可能会占用较多的内存空间。 综上所述，记忆化搜索适用于递归问题，能够减少重复计算，但可能会占用较大内存和导致栈溢出。动态规划适用于具有最优子结构的问题，通过自底向上的方式计算，但实现较为复杂且可能会占用较多内存。在实际应用中，根据问题的性质和规模选择合适的方法来解决问题。

Algorithms > Memorization Search .*
#记忆化搜索
What is Memorization Search
https://leopol1d.github.io/2023/07/25/what-is-memorization-search/
作者
Leopold
发布于
2023年7月25日
许可协议