Leetcode|651. 4键键盘(压缩成A和CV两键)

2021-09-18 16:50:49 浏览数 (1)

动态规划

题目中提到的有四个按键,但实际上,我们可以压缩为2个选择,因为对于最优解,Ctrl V一定在Ctrl A-Ctrl C两个按键后

  • dp数组含义】:按键i次后屏幕显示dp[i]A
  • 【状态】:剩余可按键数量N
  • 【选择】:①按A; ②按Ctrl V(需通过额外变量j来确定Ctrl C的位置,从而确定剪贴板中A的个数dp[j - 2]
  • 【状态转移方程】:dp[i] = max(dp[i - 1] 1, dp[j - 2] * (i - j 1));
代码语言:javascript复制
class Solution {
public:
    int maxA(int N) {
        // dp数组含义:按键i次后屏幕显示dp[i]个A
        vector<int> dp(N   1, 0);
        // 压缩为2个选择 → [1]按A;[2]按Ctrl-V (包含前方必有的Ctrl-A   Ctrl-C)
        for (int i = 1; i <= N; i  ) {
            // [1]按A
            dp[i] = dp[i - 1]   1;
            // [2]按Ctrl-V (包含前方必有的Ctrl-A   Ctrl-C)
            for (int j = 2; j < i; j  ) 
                // dp[j - 2]表示剪贴板中A的个数,减去的2即为CA   CC两个组合键
                dp[i] = max(dp[i], dp[j - 2] * (i - j   1)); // 最多可按(i - j   1)个Ctrl-V
        }
        return dp[N];
    }
};

0 人点赞