algorithm - 计算给定数字序列最多可以拆分为 K 的方式的数量

Question

大家好，我正在练习动态编程并遇到以下问题：

给定一个数 K，0 <= K <= 10^100，一个数字序列 N，有多少种可能的除法 N 使得每个部分最多为 K？

输入：

K = 8

N = 123

输出：1

解释：

123

1-23

12-3

1-2-3

拆分 N 的所有可能性，只有最后一个是有效的......

到目前为止我所取得的成就：

令 Dp[i] = 使用第 i 个数字除 N 的有效方法数。

给定一个状态，我必须使用以前的答案来计算新的答案，我们有两种可能性：

使用 dp[i-1] + 拆分数字 i 的有效方式数

使用 dp[i-1] + 不拆分数字 i 的有效方式数

但我被困在那里，我不知道该怎么办

谢谢

标签： algorithmdynamic-programming

Answer 1

使用动态规划意味着您需要从子问题的角度来考虑问题。

让我们用从索引开始N[i...]的后缀来表示（例如，用，我们有） 让我们用可能的划分方式的数量来表示，以便每个部分最多为。 我们还将使用一个小函数，它表示从 开始的“部分”的最大长度。例如，对于，我们有因为但是。 NiN = 45678955N[3...] = 78955
dp[i]N[i...]K
max_part_len(N, K, i)iN = 45678955, K = 37, i = 3max_part_len(N, K, i) = 17 < 3778 > 37

现在我们可以在 dp[i] 上写出递归（或归纳）关系。
dp[i] = sum_(j from 1 to max_part_len(N, K, i)) dp[i+j]
这种关系意味着N[i...]每个部分至多为 的可能划分方式的数量为K：对于每个满足 的 j，使得每个部分至多为
的可能划分方式的数量之和。N[i+j...]KN[i...j] <= k

如果您了解动态编程的基础知识，那么从那里算法非常简单，我将这部分留给您;-)