題目.png
private static int minOpr(int i) {
//1加匈、判斷是否適合動態(tài)規(guī)劃（略）
//2慨绳、明確參數(shù)和計算順序
//目標(biāo)為i個A時会放，給出的最小次數(shù)（子問題界定關(guān)系就是因子關(guān)系）
//3链沼、遞推函數(shù)以及初始值
if(i<1) return 0;
if(i==1) return 0;
if(i==2) return 2;
int[] res = new int[i];//i號位存儲該位置所需要最少的操作數(shù)（追蹤記錄）
res[0]=0;
res[1]=2;
res[2]=3;
//找規(guī)律（推出遞推方程）
//n=1 A min=0
//n=2 A A min=2
//n=3 A A A min=3
//n=4 AA AA min=4
//n=5 A A A A A min=5
//n=6 AAA AAA min=5
//n=7 A A A A A A A A
//n=8 AAAA AAAA
//n=9 AAA AAA AAA ......
//12 AAA AAA AAA AAA 7 || AAAA AAAA AAAA 7 || AA AA AA AA AA AA 8 || AAAAAA AAAAAA 8
//規(guī)律同一計算的因子步驟數(shù)一致
for (int x = 4; x <= i; x++) {
int minOpr=x;
double sqrt = Math.sqrt(x);
for (int y = 1; y <= sqrt; y++) {
if(y!=1){
if(x%y==0){
//是因子 除不盡全部單個黏貼和因子的最小操作數(shù)方式對比
minOpr=Math.min(minOpr,y+res[x/y-1]);
}
}
}
res[x-1]=minOpr;
}
return res[i-1];
}
