题目:
650. 2 Keys Keyboard
给你一个只有两种功能:1.复制当前萤幕上所有A 2.贴上所复制的A 两种功能的键盘
当前萤幕上有一个A，求给定n后欲贴印出n个A所需的最少operation数
思路:
对于数字i可以他的min operation数为i的所有因子的min operation数加对应倍数中
的最小值用dp表示为dp[i]=min(dp[j]+i/j) for all j, s.t i%j=0，所以照列表格即可
但其实正解应该是把他拆成数学来看递回除下去直到n=1纪录次数或是n是质数就回传n
会更快(top down)
int minSteps(int n) {
//Initially, we have one character 'A'.
vector<int> pre_ans(n+1,0);
for(int i=2;i<n+1;++i){
pre_ans[i]=i;
}
for(int i=2;i<n+1;++i){
for(int j=2;j<i;++j){
if(i%j==0){
pre_ans[i]=min(pre_ans[j]+(i/j),pre_ans[i]);
}
}
}
return pre_ans[n];
}