密码锁 (动态规划)

_algorithm · 2024-02-05 16:58:50 · 个人记录

题目描述

密码锁由n个从左到右并排的圆环组成，每个圆环上都有10个数字(0～9)，中括号内为密码显示区，每个圆环在密码显示区只能显示一个数字。可以拨动圆环来改变密码显示区显示的数字。当密码显示区的数字与密码一致时，密码锁就会被打开。

编程实现

有一个由n个圆环组成的密码锁，和一个n位的密码S(S由1～9的数字(包含1和9)组成)。每次操作只能选择一个或位置连续的多个圆环拨动。当S中的字符从左到右依次显示在密码显示区时，密码锁会被打开。

已知每个圆环在密码显示区初始数字都为0，请计算出最少需要操作多少次，才能打开密码锁。

注意：

如果选择了其中一个圆环，可将该圆环中任意一个数字拨动到密码显示区，表示1次操作；例如：将第3个圆环拨动到数字4，表示1次操作：
```
 2  6  8       2   6    3
[3  7  9] —>  [3   7   4]
 4  8  0       4   8    5
```
如果选择了位置连续的多个圆环，只能将这些圆环拨动成同一个数字，显示在密码显示区，表示1次操作。例如：将连续的第2个到第3个圆环都拨动到数字5，表示1次操作：
```
 2  6  8       2   4   4
[3  7  9] —>  [3   5   5]
 4  8  0       4   6   6
```

例如：
n =5，S="12321"；分别表示5个圆环组成的密码锁和密码12321；将5位密码1、2、3、2、1从左到右依次显示在密码显示区，以下是操作次数最少的方案：
第一次操作，将5个初始状态为0的圆环全部拨动到数字1:

 0 0 0 0 0
[1 1 1 1 1]
 2 2 2 2 2

第二次操作，将第2个到第4个圆环全部拨动到数字2:

 0 1 1 1 0
[1 2 2 2 1]
 2 3 3 3 2

第三次操作，将第3个圆环拨动到数字3:

 0 1 2 1 0
[1 2 3 2 1]
 2 3 4 3 2

最少需要操作3次，才能打开密码锁。

输入描述

第一行输入一个整数n（1<=n<=100），表示密码锁的圆环数及密码的位数
第二行输入一个长度为n的字符串S，S由1～9中的数字(包含1和9)组成，表示密码

输出描述

输出一个整数，表示最少需要操作多少次，才能打开密码锁

示例

输入：
5
12321

输出：
3

题解

要使用动态规划解决这个密码锁问题，我们需要定义合适的状态和状态转移方程，并从基本情况出发逐步构建到最终解。以下是一种可能的动态规划方法来解决这个问题：

1. 定义状态

定义 dp[i][j] 为从密码锁的第 i 个圆环到第 j 个圆环（包括 i 和 j）调整到密码所需的最小操作次数。由于密码的每个数字可以独立调整，我们需要考虑单个数字调整以及一系列连续数字调整的情况。

2. 状态转移方程

状态转移方程考虑两种情况：单独调整一个圆环或同时调整多个连续的圆环。因此，我们可以将问题分解为更小的子问题：

单个圆环调整的情况很简单，每次操作可以直接调整为目标数字，因此操作次数为 1。
对于多个连续的圆环，如果S[k] == S[j]，即k位置和j位置对应的密码相等，那么可以将k和j之间的圆环一起拨动，操作次数减一

因此，状态转移方程可以表示为：

状态转移方程：如果S[k] == S[j] : dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] - 1)

否则，动态规划方程为: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

其中，i ≤ k < j，这意味着我们尝试将区间 [i, j] 分割成两部分 [i, k] 和 [k+1, j]，并对这两部分分别进行调整，最后加上将整个区间调整到一致所需的操作次数。

3. 基本情况

当 i = j 时，dp[i][j] = 1，因为调整单个圆环到目标数字只需要一次操作。

4. 实现步骤

代码中，由内到外、由小到大依次计算每个区间长度为len的子问题，保证了在计算dp[i][j]时，dp[i][k]和dp[k+1][j]已经计算出来。
动态规划方程中，dp[i][j]在开始时应该初始化为一个较大的值，也就是区间长度，即最坏情况下的操作次数。
代码中，dp数组的下标是从0开始的，所以要注意数组下标和密码、圆环的位置之间的对应关系。计算第i个到第j个圆环的操作次数时，对应的是dp[i-1][j-1]。

示例代码

#include <bits/stdc++.h>
using namespace std;
int n;
string S;
int minOperations() {
    int dp[2005][2005] = {};
    // 预处理，直接设置单个圆环的操作次数为1
    for (int i = 0; i < n; ++i) dp[i][i] = 1;
    // 处理长度大于1的区间
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            dp[i][j] = len; // 初始化为区间长度，即最坏情况下的操作次数
            for (int k = i; k < j; ++k) {
                if (S[k] == S[j]) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] - 1);
                else dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
    }
    return dp[0][n-1];
}
int main() {
    cin >> n >> S;
    cout << minOperations() << endl;
    return 0;
}