leetcode - 650. 2 Keys Keyboard 【动态规划 + 质数 & 非质数 + 简洁表达】

题目

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

1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
2. Paste: You can paste the characters which are copiedlast 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 getn 'A'.

Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Note:

1. The n will be in the range [1, 1000].

题意

最初在笔记本中只有一个字符“A”.你可以进行如下两种操作：

1.copy all：你可以将笔记本中的所有字母都进行复制（不支持复制部分）。

2.Paste: 将最后一次赋值的内容进行粘贴。

分析及解答

解答1：(原具体解答)

   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];
    }

解答2：(具体解答：原具体解答)

public int minSteps(int n) {
    int res = 0;
    for(int i=2;i<=n;i++){
        while(n%i == 0){
            res+= i;
            n=n/i;
        }
    }
    return res;
}