2 Keys Keyboard

https://leetcode.com/problems/2-keys-keyboard/description/

Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).

Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.

Thoughts

先从1个开始往下写。发现4是可以写成C->P->C->P和C->P->P->P两种。前者相当于把2的C->P结果复制再粘贴。再往后6也可以写成两个3的C->P->P，即C->P->P->P (1:3)->C(3:3)->P(3:6)五步， 或者C->P->C(2:2)->P(2:4)->P(2:6)四步. 因此我们可以把已知的结果复制，再粘贴数次得到不同i的一种分解法。我们在每次得到一个新的分解方法时看下它是不是比已知值小即可。这时我们可以看出，只要不是质数都可以用这种方法把所有可能性拼出来，但对于质数只能不断+1, 因此，还有种f[i] = i的解法单独给质数。

Code

class Solution {
    public int minSteps(int n) {
        int[] f = new int[n + 1];
        if (n == 1) {
            return f[1];
        }
        f[2] = 2;
        for (int i = 2; i <= n; i++) {
            if (i % 2 != 0) {
                if (f[i] == 0) {
                    f[i] = i;
                } else {
                    f[i] = Math.min(i, f[i]);
                }
            }

            int j = 1, index = i * (j + 1), steps = f[i] + 1 + j; 

            while (index <= n) {
                if (f[index] == 0) {
                    f[index] = steps;
                } else {
                    f[index] = Math.min(f[index], steps);
                }
                //System.out.println(i + ", " + f[i] + ": " + index + ", " + f[index]);
                j++;
                index = i * (j + 1);
                steps = f[i] + 1 + j;
            }

        }

        return f[n];
    }
}

Analysis

做题耗时: 1小时。

Errors:

1. 以为奇数只有f[i] = i一种解法，以及认为偶数f[i] = f[i/2] + 2一定最优。

2. j, index和steps的关系搞混

时间复杂度为O(n^2).

Ver.2

想让操作数最少, 那尽量让每次复制的数目j够多. 为了不会超出N, 还必须 N % j == 0. 因此我们让i从2遍历到N, 让j作为每次能复制的数目, 从i - 1遍历到2. 遇到的第一个能被i整除的j停止即可.

class Solution {
    public int minSteps(int n) {
        int[] f = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            f[i] = i;
            for (int j = i - 1; j >= 2; j--) {
                if (i % j == 0) {
                    f[i] = f[j] + i / j;
                    break;
                }
            }
        }

        return f[n];
    }
}