Module: 动态规划中的模式


Problem

1 /7


消息数

Theory Click to read/hide

免责声明:下面描述的方法并不通用,但它通常可以解决问题或帮助您找到正确的解决方案。

如果问题归结为需要以最佳方式(或计算合适的拆分次数)将数组拆分为不相交的子段(一系列连续元素),那么值得尝试解决它使用动态规划。

示例解决方案如下:
dp[i] - 对前 i 个元素的响应

计算 dp[i]:因为我们只考虑前 i 个元素,所以第 i 个元素将是最后一个,这意味着该元素将在最后一个子段中,同时也是那里最右边的一个。因此,我们可以迭代最后一个子段 j 的左边界。在枚举的过程中,我们会计算这个subsegment的值,如果正确,那么我们会重新计算dp[i]到dp[j - 1]和subsegment[j;i]的值。

考虑以下简单问题:给定一个整数数组,您需要将其拆分为最少数量的不相交子段,以便每个数字都包含在某个子段中,并且每个子段包含相同的数字。例如,对于数组 1 2 2 3 3 3 2 1 1,最佳分区如下所示:[1] [2 2] [3 3 3] [2] [1 1]。这个任务很容易通过简单地遍历数组来解决(我们将所有相同的连续元素放在一个子段中),但我们将使用动态规划来解决它作为一个例子。
  国际; 辛>>名词; // 用 1-index 填充数组 矢量 arr(n + 1); for (int i = 1; i <= n; i++) 辛>>到达[我]; // 最初将 +oo 设置为 dp 值 矢量 dp(n + 1, 1000000000); // 长度为零的数组不需要拆分,所以它的答案是 0 dp[0] = 0; // 将 dp[i] 的答案按 i 升序计数 对于 (int i = 1; i <= n; i++) { // 当前 arr[i] 是最后一个元素,因此它将是最后一个子段中最右边的数字 // 遍历最后一个子段开始位置的所有选项 for (int j = i; j > 0; j--) { 如果 (arr[j] != arr[i]) { // 如果遇到不等于最后一个的元素,那么子段会包含不同的数字,这不符合条件 // 继续没有意义,因为将左边框向左移动,这个元素不会消失,所以我们 break 休息; } // 假设最后一个子片段是 [j;i] // 所以你需要对前 j-1 个元素进行最优划分并加 1(子段 [j; i] 本身) dp[i] = min(dp[i], dp[j - 1] + 1); } } 输出 << dp[n];
如果元素可能不属于任何子段,那么您只需要考虑适当的选项,如 dp[i] = dp[i - 1]

Problem

在仅由俄语字母和空格组成的消息中,每个字母都被其在俄语字母表中的序列号(A – 1、B – 2、…、I – 33)和空格 – 替换。零。 
给定一个给定的数字序列,需要找到可以从中获得它的原始消息的数量。

输入:
第一行包含不超过 70 位数字的序列。

输出:
打印一个数字 - 可能的消息数。

示例:
  <正文>
输入 输出
1025 4