leetcode 651

问题

Imagine you have a special keyboard with the following keys:

Key 1: (A): Print one ‘A’ on screen.

Key 2: (Ctrl-A): Select the whole screen.

Key 3: (Ctrl-C): Copy selection to buffer.

Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of ‘A’ you can print on screen.

Example 1:

1
2
3
4
5
Input: N = 3
Output: 3
Explanation: 
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2:

1
2
3
4
5
Input: N = 7
Output: 9
Explanation: 
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Note:

  1. 1 <= N <= 50
  2. Answers will be in the range of 32-bit signed integer.

分析

思路1: $DP[i]$ 表示 $i$ 次操作之后所能获得的最大的 $A$ 的个数。$DP[i]$ 的获得可以分两种情况，一种情况是没有没有使用“复制”，这种情况下 $DP[i]$ 就是 $i$ ，另一种情况是使用了“复制”，那我们可以假设最后一次复制得到 $DP[i]$ ，是由于 $DP[i-1] DP[j]$ ，那么可以有$DP[i] = DP[j](i-j-1)$ ，其中 $0 \leq j < i-1$ 。因此，对于每一个 $i$ 可以通过两次循环来进行求解。时间复杂度 $O(N^2)$ 。

思路2: 通过模拟的方式，从低次数到搞次数，将存在的 $A$ 的个数的可能以及 $buffer$ 中 $A$ 的个数都表示出来，然后在根据大小判断进行剪枝。方案较为笨重，时间复杂度高。经过测试 $N$ 约等于 50 的时候就已经有一万多种可能性了。虽然剪枝能够让时间复杂度降低很多，但还是按照 $O(2^N)$ 来进行估计吧。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// O(n^2)
class Solution {
public:
    int maxA(int N) {
        vector<int> dp(N+1, 0);
        for (int i = 1; i <= N; ++i) {
            dp[i] = i;
            for (int j = 1; j < i-1; ++j) {
                dp[i] = max(dp[i], dp[j]*(i-j-1));
            }
        }
        return dp[N];
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxA(int N) {
        vector<set<pair<int,int>, greater<pair<int,int>>>> dp(N+1);
        
        dp[1].insert({1,1});
        for (int i = 1; i < N; ++i) {
            int buffer = -1;
            cout << dp[i].size() << endl;
            for (auto it = dp[i].begin(); it != dp[i].end(); ++it) {
                if (it->second <= buffer) continue;
                if (i+1 <= N) dp[i+1].insert({it->first+it->second, it->second});
                if (i+3 <= N) dp[i+3].insert({it->first * 2, it->first});
            }
        }
        return dp[N].begin()->first;
    }
};