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