650. 2 Keys Keyboard

class Solution {
    public int minSteps(int n) {
        int MAX = Integer.MAX_VALUE / 2;

        // 定义 dp[i][j] 为打印出 i 个 'A' 且当前剪切板字符数为 j 时的最少操作次数
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], MAX);
        }
        dp[1][0] = 0; // 未进行任何操作时，此时打印出一个 'A' 且剪切板无字符
        dp[1][1] = 1; // 进行了一次复制，此时打印出一个 'A', 剪切板字符数为 1

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (i != j) {
                    // 说明最后一步为粘贴，且粘贴的字符数为 i - j
                    dp[i][j] = dp[i - j][j] + 1;
                } else {
                    // i == j, 说明最后一步为复制，但是我们不知道从哪一步复制而来，所以只能 for 循环获取最少操作次数
                    for (int k = 0; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + 1);
                    }
                }
            }
        }

        int res = MAX;
        for (int j = 0; j <= n; j++) {
            res = Math.min(res, dp[n][j]);
        }
        return res;
    }
}

References

650. 2 Keys Keyboard