LeetCode 1079 活字印刷

Ciel Yang 收录于类别练习 OJ解题报告

2023-05-22 2023-05-22 约 756 字预计阅读 2 分钟

本题考察了对于离散数学中各种组和数相关公式的使用。

题目描述

原题链接如下： LeetCode 1079 活字印刷

题目大意

字模取值范围是 26 个大写英文字母，同时必须注意字模可能有重复。

输入与输出

3 个输入分别是：

1
2
3
4
5
6
7
8
Input 1:
AAB

Input 2:
AAABBC

Input 3:
V

对应的输出分别是：

1
2
3
4
5
6
7
8
Output 1:
8

Output 2:
188

Output 3:
1

解题思路

本题的数据规模极小，直接暴力枚举也可通过，但是更好的办法是通过组合数学推到出动态规划的解法。

首先，需要先整合处理所有重复的字模，直接遍历的同时进行计数，可以得到具体的每个字模的数量。

然后，假设 $dp[i][j]$ 代表用前 i 种字符构造长度为 j 的字符序列的方案数。如果从第 i 种字模中选择 k 个填入字符序列，剩余位置组成的序列长度为 $j - k$，此时对应的方案数为 $dp[i - 1][j - k] \cdot C_{j}^{k}$。所以，不断枚举 k 并且累加各个对应的方案数，最后的结果就是 $dp[i][j]$，即：

$$ dp[i][j] = \sum_{k=0}^{\min(j,c)} dp[i-1][j-k] \cdot C_{j}^{k} $$

使用 0 种字模构建 0 长度的序列的方案数为 1，即初始值 $dp[0][0]$ 为 1。

最后，累加所有可能的长度（从 1 开始）对应的方案数即可。

代码

实际的编码过程中可以注意到递推公式中 $dp[i]$ 只和 $dp[i-1]$ 有关，可以使用一维数组代替二位数组节省空间，当然要注意内部循环遍历的时候要从后往前
组合数的求解需要处理阶乘或者连续的乘法，而本题的数据规模较小，可以利用公式 $C_{i}^{j} = C_{i-1}^{j-1} + C_{i-1}^{j}$ 来迭代计算
迭代计算动态规划的记录时可以累加已经使用的字模数量作为序列长度的最大值，可以些微加速计算

 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
class Solution {
    private val c = Array(MX) { IntArray(MX) }

    init {
        for (i in c.indices) {
            c[i][0] = 1
            c[i][i] = 1
            for (j in 1 until i) {
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
            }
        }
    }

    fun numTilePossibilities(tiles: String): Int {
        val counter = IntArray(TOTAL)
        for (c in tiles) {
            counter[c - 'A']++
        }
        val dp = IntArray(tiles.length + 1)
        dp[0] = 1
        var t = 0
        for (cnt in counter) {
            if (cnt == 0) continue
            t += cnt // slightly faster than (n downTo 1)
            for (j in t downTo 1) for (k in 1..minOf(j, cnt)) {
                dp[j] += dp[j - k] * c[j][k]
            }
        }
        return dp.sum() - 1
    }

    companion object {
        private const val MX = 8
        private const val TOTAL = 26
    }
}

目录

LeetCode 1079 活字印刷

题目描述

题目大意

输入与输出

解题思路

代码