记忆化搜索

87. 扰乱字符串

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:

    vector<vector<vector<int>>> cache;
    int Y = 1, N = -1;
    string s1, s2;
    bool isScramble(string _s1, string _s2) {
        s1 = _s1, s2 = _s2;
        if (s1 == s2) return true;
        if (s1.size() != s2.size()) return false;
        int n = s1.size();
        // cache表示s1从i开始，s2从j开始 len 位，是否形成扰动字符串
        cache.resize(n, vector<vector<int>>(n, vector<int>(n + 1, 0)));
        return dfs(0, 0, n);
    }

    bool dfs(int i, int j, int len) {
        if (cache[i][j][len] != 0) return cache[i][j][len] == Y;
        string a = s1.substr(i, len), b = s2.substr(j, len);
        if (a == b){
            cache[i][j][len] = Y;
            return true;
        } 
        if (!check(a, b)) {
            cache[i][j][len] = N;
            return false;
        }

        for (int k = 1; k < len; k ++) {
            if (dfs(i, j, k) && dfs(i + k, j + k, len - k)) {
                cache[i][j][len] = Y;
                return true;
            }
            if (dfs(i, len - k + j, k) && dfs(i + k, j, len - k)) {
                cache[i][j][len] = Y;
                return true;
            }
        }
        cache[i][j][len] = N;
        return false;
    }

    bool check(string a, string b) {
        if (a.size() != b.size()) return false;

        vector<int> cnt1(26, 0), cnt2(26, 0);
        for (auto c: s1) {
            cnt1[c - 'a'] ++;
        }
        for (auto c: s2) {
            cnt2[c - 'a'] ++;
        }
        return cnt1 == cnt2;
    }
};

375. 猜数字大小 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:

    vector<vector<int>> cache;

    int getMoneyAmount(int n) {
        cache.resize(n + 1, vector<int>(n + 1, 0));
        return dfs(1, n);
    }

    int dfs(int l, int r) {
        if (l >= r) return 0;
        if (cache[l][r] != 0) return cache[l][r];
        int ans = 0x3f3f3f3f;
        for (int x = l; x <= r; x ++) {
            int cnt = max(dfs(l, x - 1), dfs(x + 1, r)) + x;
            ans = min(ans, cnt);
        }
        cache[l][r] = ans;
        return ans;
    }
};

403. 青蛙过河

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
28
29
30
31
32
class Solution {
public:

    unordered_map<string, bool> cache; // 存储u下标跳k步有没有方案
    unordered_map<int, int> map; // 存储每个石块对应的下标

    bool canCross(vector<int>& stones) {
        int n  = stones.size();
        for (int i = 0; i < n; i ++) {
            map.insert({stones[i], i});
        }
        if (!map.count(1)) return false;
        return dfs(stones, n, 1, 1);
    }

    bool dfs(vector<int> &stones, int n, int u, int k) {
        if (u == n - 1) return true;
        string key = to_string(u) + '_' + to_string(k);
        if (cache.count(key)) return cache[key];
        for (int i = -1; i <= 1; i ++) {
            if (k + i == 0) continue;
            int next = stones[u] + i + k;  // 下一个跳跃点
            if (map.count(next)) {
                bool cur = dfs(stones, n, map[next], k + i);
                cache.insert({key, cur});
                if (cur) return true;
            }
        }
        cache.insert({key, false});
        return false;
    }
};

494. 目标和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:

    unordered_map<string, int> cache; // 表示从u下标,当前计算结果为string，的方案数int

    int findTargetSumWays(vector<int>& nums, int target) {
        return dfs(nums, target, 0, 0);
    }

    int dfs(vector<int> &nums, int target, int u, int cur) {
        string key = to_string(u) + '_' + to_string(cur); 
        if (cache.count(key)) return cache[key];
        if (u == nums.size()) {
            cache.insert({key, cur == target ? 1: 0});
            return cache[key];
        }
        int left = dfs(nums, target, u + 1, cur - nums[u]);
        int right = dfs(nums, target, u + 1, cur + nums[u]);
        cache.insert({key, left + right});
        return cache[key];
    }
};

552. 学生出勤记录 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    // cache 是指 下标为u，连续a个数为acnt，l个数为lcnt的方案数
    vector<vector<vector<int>>> cache;
    int mod = (int)1e9 + 7;
    int checkRecord(int n) {
        cache.resize(n + 1, vector<vector<int>>(2, vector<int>(3, -1)));
        return dfs(n, 0, 0);
    }

    int dfs(int u, int acnt, int lcnt) {
        if (acnt >= 2) return 0;
        if (lcnt >= 3) return 0;
        if (u == 0) return 1;
        if (cache[u][acnt][lcnt] != -1) return cache[u][acnt][lcnt];
        int ans = 0;
        ans = dfs(u - 1, acnt + 1, 0) % mod;  // A
        ans = (ans + dfs(u - 1, acnt, lcnt + 1)) % mod; // L
        ans = (ans + dfs(u - 1, acnt, 0)) % mod; // P
        cache[u][acnt][lcnt] = ans;
        return ans;
    }
};

576. 出界的路径数

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:

    vector<vector<vector<int>>> cache;
    int MOD = (int) 1e9 + 7;

    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        cache.resize(maxMove + 1, vector<vector<int>>(m, vector<int>(n, -1)));
        return dfs(m, n, maxMove, startRow, startColumn);
    }

    int dfs(int m, int n, int u, int x, int y) {
        if (x >= m || x < 0) return 1;
        if (y >= n || y < 0) return 1;
        if (u == 0) return 0;
        if (cache[u][x][y] != -1) return cache[u][x][y];
        int ans = 0;
        ans = dfs(m, n, u - 1, x + 1, y) % MOD;
        ans = (ans + dfs(m, n, u - 1, x, y + 1)) % MOD;
        ans = (ans + dfs(m, n, u - 1, x, y - 1)) % MOD;
        ans = (ans + dfs(m, n, u - 1, x - 1, y)) % MOD;
        cache[u][x][y] = ans;
        return ans;
    }
};

1137. 第 N 个泰波那契数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:

    int cache[40];
    
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        if (cache[n] != 0) return cache[n];
        cache[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
        return cache[n];
    }
};

剑指 Offer 10- I. 斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:

    int mod = (int) 1e9 + 7;
    int cache[110];

    int fib(int n) {
        if (n <= 1) return n;
        if (cache[n] != 0) return cache[n];
        cache[n] = fib(n - 1) + fib(n - 2);
        cache[n] %= mod;
        return cache[n];
    }
};

638. 大礼包 

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
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:

    vector<int> price;
    vector<vector<int>> special;
    vector<int> needs;
    map<vector<int>, int> cache;

    int shoppingOffers(vector<int>& _price, vector<vector<int>>& _special, vector<int>& _needs) {
        price = _price;
        special = _special;
        needs = _needs;
        return dfs(needs);
    }

    int dfs(vector<int> needs) {
        if (cache.count(needs)) {
            return cache[needs];
        }
        int n = needs.size();
        int minN = 0;
        for (int i = 0; i < n; i ++) {
            minN += price[i] * needs[i];
        }

        for (int i = 0; i < special.size(); i ++) {
            bool flag = true;
            vector<int> nextNeeds = needs;
            for (int j = 0; j < n; j ++) {
                if (special[i][j] > nextNeeds[j]) flag = false;
                nextNeeds[j] -= special[i][j];
            }
            if (!flag) continue;
            minN = min(minN, dfs(nextNeeds) + special[i][n]);
        }
        return cache[needs] = minN;
    }
};
算法
#DP #记忆化搜索
记忆化搜索
https://2w1nd.github.io/2022/01/30/算法/理论算法/记忆化搜索/
作者
w1nd
发布于
2022年1月30日
许可协议