650. 2 Keys Keyboard

一道数学找规律的题。我一开始思路错了。后来发现n = 9，21之类的case不太对。
其实最后我也没能证明这个解法是对的，只是试了很多种case都可以过。
看一个数能否被分解成两个整数的product的方法:while (i / divider * divider != i)挺好的。

    public int minSteps(int n) {
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        dp[2] = 2;
        for (int i = 3; i <= n; i = i + 1) {
            int divider = i - 1;
            while (i / divider * divider != i) {
                divider--;
            }
            dp[i] = dp[divider] + i / divider;
        }
        return dp[n];
    }

DISCUSSION里的：

    public int minSteps(int n) {
        int[] dp = new int[n+1];

        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = i-1; j > 1; j--) {
                if (i % j == 0) {
                    dp[i] = dp[j] + (i/j);
                    break;
                }
                
            }
        }
        return dp[n];
    }

--