→ dont: 大師 08/19 14:02
題目:
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];
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.229.93 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724028459.A.AE8.html