leetcode650. 隻有兩個鍵的鍵盤

思路

1. 質數隻能一個一個複制黏貼，因為可以省事的次數全都是有除數的，有倍數關系的
2. 比如4，是2的倍數，可以由2複制黏貼一次得到，9是3的倍數，可以由3複制黏貼黏貼得到，最小的除數才是最省事的，這樣可以使黏貼的次數最少，比如12，由6得到總比3以及4得到要快

代碼

int isOK(int n){
    int len=sqrt(n);
    int i;
    int flag = 0;
    for(i=2;i<=len;i++){
        if(n%i==0){
            flag = 1;
            break;
        }
    }
    return flag;
}

int minSteps(int n){
    if(n==1)
        return 0 ;
    int i,j;
    int flag = isOK(n);
    if(flag==0)//質數直接傳回
        return n;
    int f[1001]={0};
    f[1] = 0;
    f[2] = 2;
    f[3] = 3;
    for(i=4;i<=n;i++){
        int l = sqrt(i);
        for(j=2;j<=l;j++){
            if(i%j==0){
                f[i] = f[i/j] + j;//眼拙 老寫成n
                break;
            }
        }
        if(f[i]==0)//眼拙 老寫成n
            f[i] = i;
    }
    return f[n];
    
}