Leetcode 2218. Maximum Value of K Coins From Piles

[Woodyiiiiiii]

类似题目：

• 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

---

No.2218.

第一眼就想到用Brutal Force暴力搜索所有可能(几乎所有同类型题的正常思路)：

class Solution {
    List<List<Integer>> piles;

    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        // copy piles to this.piles
        this.piles = new ArrayList<>();
        for (List<Integer> pile : piles) {
            this.piles.add(new ArrayList<>(pile));
        }
        return dfs(k);
    }

    private int dfs(int k) {
        if (k == 0) {
            return 0;
        }
        int max = 0;
        for (List<Integer> pile : piles) {
            if (pile.size() == 0) {
                continue;
            }
            int value = pile.get(0);
            pile.remove(0);
            max = Math.max(max, value + dfs(k - 1));
            pile.add(0, value);
        }
        return max;
    }
}

但显然是超时的，一定要进行记忆化搜索优化。

这是Top-down DP的算法类型。已知变量有piles.length、k，根据他们的最大值，所以我们不妨设dp[piles.length+1][k+1]，dp[i][j]用来表示从i到n-1的piles中取k个coins的最大值。两者加一作为长度是防止爆栈。

然后通过DFS，选或不选的写法进行递归。

class Solution {
    List<List<Integer>> piles;
    Integer[][] memo;

    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        // copy piles to this.piles
        this.piles = new ArrayList<>();
        for (List<Integer> pile : piles) {
            this.piles.add(new ArrayList<>(pile));
        }
        memo = new Integer[piles.size() + 1][k + 1];
        return dfs(0, k);
    }

    private int dfs(int i, int k) {
        if (i == piles.size() || k == 0) return 0;
        if (memo[i][k] != null) return memo[i][k];

        int res = dfs(i + 1, k);
        int cur = 0;
        for (int j = 0; j < Math.min(k, piles.get(i).size()); j++) {
            cur += piles.get(i).get(j);
            res = Math.max(res, cur + dfs(i + 1, k - j - 1));
        }

        return memo[i][k] = res;
    }
}

空间复杂度是 O(nk)，时间复杂度是O(mk)，其中，m=sum(piles[i].length) <= 2000，刚好用到了题目条件。

---

No.1639.

这题同样是Top-down DP。先从DFS+记忆化搜索开始，根据选或不选写法，同时注意的是从底部收敛到上一层的转移函数是乘法，同时为了防止乘法后爆栈，需要用long存储：

class Solution {
    String target;
    String[] words;
    int[][] dict;
    long[][] memo;
    final int MOD = 1000000007;

    public int numWays(String[] words, String target) {
        int len = words[0].length(), m = target.length();
        if (len < m) return 0;
        this.target = target;
        this.words = words;
        dict = new int[len][26];
        // init dict
        for (int i = 0; i < len; ++i) {
            for (String word : words) {
                dict[i][word.charAt(i) - 'a']++;
            }
        }
        // init memo
        memo = new long[len][m];
        return (int) dfs(0, 0);
    }

    private long dfs(int start, int idx) {
        if (idx == target.length()) return 1;
        if (start == words[0].length() || words[0].length() - start < target.length() - idx) return 0;
        int res = 0;
        if (memo[start][idx] != 0) return memo[start][idx];
        if (dict[start][target.charAt(idx) - 'a'] > 0) {
            long t = dfs(start + 1, idx + 1);
            t *= dict[start][target.charAt(idx) - 'a'];
            t %= MOD;
            res += t;
        }
        res += dfs(start + 1, idx);
        res %= MOD;
        return memo[start][idx] = res;
    }
}

---

No.1537.

注意取模的问题。因为要比较，所以比较前不能取模，只能最后取了。