650.2 Keys Keyboard

Posted on | In

Solution 1: accepted 28ms

DP.

  1. Base case: A[1] = 0
  2. Induction rule: A[n]
    if n%2 == 0, A[n] = dp[n] + 2
    if n%2 != 0, A[n] = max(dp[j] + n/j), where n%j = 0 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minSteps(int n) {
        if (n < 1) {
            return 0;
        }
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (i % 2 == 0) {
                dp[i] = dp[i / 2] + 2;
            } else {
                for (int j = 3; j < i / 2; j++) {
                    if (i % j == 0 && dp[j] != 0) {
                        dp[i] = dp[j] + (i / j);
                    }
                }
                if (dp[i] == 0) {
                    dp[i] = i;
                }
            }
        }
        return dp[n];
    }
}