650.只有两个键的键盘（动态规划）

解题思路：动态规划

对于一个数n，他需要进行多少次的复制全部和粘贴的操作，比如25个A，最大能被25整除（比25小的数中）2的数是5，那么我需要复制5个A粘贴5次就可以得到25个A，那么怎么得到5个A，最大能被5整除（比5小的数中）的数是1，因此只能通过复制一个A并粘贴5次。

假设 n%m=0,n/m=min_val; m的范围[1,n-1]；
那么动态转移方程为：
dp[n]=dp[m]+（min_val-1）+1;
dp[m]代表要得到m个A最少需要多少次操作；
min_val-1代表需要对m个A进行粘贴的次数；
最后+1是复制m个A的次数。

class Solution {
    
public:
    int minSteps(int n) {
    
        //找[1,n-1]最大能被n整除的
        //16/8=2；那么就是dp[16]=dp[8]+2-1;dp[8]=dp[4]+2-1;dp[4]=dp[2]+2-1;dp[2]=dp[1]+2-1;
        vector<int>dp(n+1);
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<=n;++i){
    
            int min_val=INT_MAX;
            int index;
            for(int j=i-1;j>=1;--j){
    
                if(i%j==0){
    
                    int val=i/j;
                    if(val<min_val){
    
                        min_val=val; //最少的粘贴次数
                        index=j;     //在哪个位置粘贴
                    }
                }
            }
            dp[i]=dp[index]+min_val-1+1;
        }
        return dp[n];
    }
};