Leetcode [650] 只有两个键的键盘 & Leetcode [651] 四键键盘 动态规划

/*
 * @lc app=leetcode.cn id=650 lang=cpp
 *
 * [650] 只有两个键的键盘
 *
 * https://leetcode-cn.com/problems/2-keys-keyboard/description/
 *
 * algorithms
 * Medium (52.48%)
 * Likes:    279
 * Dislikes: 0
 * Total Accepted:    21.6K
 * Total Submissions: 41K
 * Testcase Example:  '3'
 *
 * 最初在一个记事本上只有一个字符 'A'。你每次可以对这个记事本进行两种操作：
 * 
 * 
 * Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
 * Paste (粘贴) : 你可以粘贴你上一次复制的字符。
 * 
 * 
 * 给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 'A'。输出能够打印出 n 个 'A' 的最少操作次数。
 * 
 * 示例 1:
 * 
 * 
 * 输入: 3
 * 输出: 3
 * 解释:
 * 最初, 我们只有一个字符 'A'。
 * 第 1 步, 我们使用 Copy All 操作。
 * 第 2 步, 我们使用 Paste 操作来获得 'AA'。
 * 第 3 步, 我们使用 Paste 操作来获得 'AAA'。
 * 
 * 
 * 说明:
 * 
 * 
 * n 的取值范围是 [1, 1000] 。
 * 
 * 
 */

思路：

当n = 1时，已经有一个A了，我们不需要其他操作，返回0

当n = 2时，我们需要复制一次，粘贴一次，返回2

当n = 3时，我们需要复制一次，粘贴两次，返回3

当n = 4时，这就有两种做法，一种是我们需要复制一次，粘贴三次，共4步，另一种是先复制一次，粘贴一次，得到AA，然后再复制一次，粘贴一次，得到AAAA，两种方法都是返回4

当n = 5时，我们需要复制一次，粘贴四次，返回5

当n = 6时，我们需要复制一次，粘贴两次，得到AAA，再复制一次，粘贴一次，得到AAAAAA，共5步，返回5

可以看出对于n，至多需要n步，即cppppp....，而如果可以分解成相同的几份，则可以减少次数，比如n=6时，目标是AAAAAA，可以分解为两个AAA或者三个AA，所以递推公式为：

dp[i] = min(dp[i], dp[j] + i / j);
i为1~n，j为1~i，i为外循环，j为内循环

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n+1,n);
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<=n;++i){
            dp[i]=i;
            for(int j=2;j<=i/2;++j){
                if(i%j==0){
                    dp[i]=min(dp[i],dp[j]+i/j);
                }
            }
        }
        return dp[n];
    }
};

【四键键盘】

假设你有一个特殊的键盘包含下面的按键：

Key 1: (A)：在屏幕上打印一个 'A'。

Key 2: (Ctrl-A)：选中整个屏幕。

Key 3: (Ctrl-C)：复制选中区域到缓冲区。

Key 4: (Ctrl-V)：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。

现在，你只可以按键 N 次（使用上述四种按键），请问屏幕上最多可以显示几个 'A'呢？

样例 1:

输入: N = 3
输出: 3
解释:
我们最多可以在屏幕上显示三个'A'通过如下顺序按键：
A, A, A
 

样例 2:

输入: N = 7
输出: 9
解释:
我们最多可以在屏幕上显示九个'A'通过如下顺序按键：
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
 

注释:

1 <= N <= 50
结果不会超过 32 位有符号整数范围。

思路：labuladong

这个算法基于这样一个事实，最优按键序列一定只有两种情况：

要么一直按A：A,A,…A（当 N 比较小时）。

要么是这么一个形式：A,A,…C-A,C-C,C-V,C-V,…C-V（当 N 比较大时）

最后一次按键要么是A要么是C-V。明确了这一点，可以通过这两种情况来设计算法

int[] dp = new int[N + 1];
// 定义：dp[i] 表示 i 次操作后最多能显示多少个 A
for (int i = 0; i <= N; i++) 
    dp[i] = max(
            这次按 A 键，
            这次按 C-V
        )

对于「按A键」这种情况，就是状态i - 1的屏幕上新增了一个 A 而已，很容易得到结果：

// 按 A 键，就比上次多一个 A 而已
dp[i] = dp[i - 1] + 1;

刚才说了，最优的操作序列一定是C-A C-C接着若干C-V，所以我们用一个变量j作为若干C-V的起点。那么j之前的 2 个操作就应该是C-A C-C了

class Solution {
public:
    int maxA(int n) {
        vector<int> dp(n+1,0);
        dp[0]=0;
        for(int i=1;i<=n;++i){
            dp[i]=dp[i-1]+1; // A
            for(int j=2;j<i;++j){
                dp[i]=max(dp[i],dp[j-2]*(i-j+1));
            }
        }
        return dp[n];
    }
};