Leetcode 1553. Minimum Number of Days to Eat N Oranges

[Woodyiiiiiii]

这道题是一道经典的记忆化搜索 / DP问题。

这种有股预知性的题目，一般都是在过程中比较，然后用缓存缩减重复时间：）

也就是所谓的记忆化搜索。

记忆化搜索/状态压缩都是记录递归中重复的进程状态。

用全局Map来加快时间；然后递归+缓存。

class Solution {
    Map<Integer, Integer> dp = new HashMap<>();
    public int minDays(int n) {
        if (n <= 1)
            return n;
        if (!dp.containsKey(n))
            dp.put(n, 1 + Math.min(n % 2 + minDays(n / 2), n % 3 + minDays(n / 3)));
        return dp.get(n);
    }
}

---

• 1553. Minimum Number of Days to Eat N Oranges

---

类似题目：

• 1641. Count Sorted Vowel Strings

---

• 87. Scramble String

2023/03/30
这道题也挺有意思。看到字符串长度最大是30，我就考虑到要用到DFS+记忆化搜索。但我在DFS中摘除了字符串s2的考虑，进而无法想到如何使用Map来缩短时间，导致TLE。

class Solution {
    Map<String, Boolean> map = new HashMap<>();

    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) {
            return true;
        }
        return dfs(s1, s2);
    }

    private boolean dfs(String s1, String s2) {
        if (s1.equals(s2)) {
            return true;
        }
        if (s1.length() != s2.length()) {
            return false;
        }
        if (s1.length() == 1) {
            return false;
        }
        String key = s1 + " " + s2;
        if (map.containsKey(key)) {
            return map.get(key);
        }
        for (int i = 1; i < s1.length(); ++i) {
            boolean swap = dfs(s1.substring(0, i), s2.substring(s2.length() - i)) && dfs(s1.substring(i), s2.substring(0, s2.length() - i));
            boolean noSwap = dfs(s1.substring(0, i), s2.substring(0, i)) && dfs(s1.substring(i), s2.substring(i));
            if (swap || noSwap) {
                map.put(key, true);
                return true;
            }
        }
        map.put(key, false);
        return false;
    }
}

---

1786. Number of Restricted Paths From First to Last Node

注意memo缓存数组要一开始赋值-1，标记未访问，否则如果是0则有可能被误认。

---

2218. Maximum Value of K Coins From Piles
1639. Number of Ways to Form a Target String Given a Dictionary
1537. Get the Maximum Score
1786. Number of Restricted Paths From First to Last Node