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 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’.
• Example 1:

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

• 題目大意：給定一個筆記本，目前含有一個字元A，可以做複制與粘貼操作，求給定一個數字n，需要執行多少步操作，使字元數達到n個。
• 思路：dp dp[i]=min(dp[i],dp[i]+i/j) i是j的整數倍，如果i是j的整數倍，則i可以通過粘貼i/j-1次得到j，再加上一次複制，為i/j，dp[j]表示當n等于j時最小的步驟，是以可以通過dp[j]+i/j得到dp[i]。
• 代碼

  package DP;
  
  /**
  * @Author OovEver
  * @Date 2017/12/15 10:18
  */
  public class LeetCode650 {
    public int minSteps(int n) {
        int[] dp = new int[n + ];
        for(int i=;i<=n;i++) {
  //            所需最大次數，則複制一次，一直粘貼
            dp[i] = i;
            for(int j=i-;j>;j--) {
                if (i % j == ) {
                    dp[i] = dp[j] + (i / j);
                    break;
                }
            }
        }
        return dp[n];
    }
  }