题目.png
private static int minOpr(int i) {
//1、判断是否适合动态规划（略）
//2、明确参数和计算顺序
//目标为i个A时，给出的最小次数（子问题界定关系就是因子关系）
//3、递推函数以及初始值
if(i<1) return 0;
if(i==1) return 0;
if(i==2) return 2;
int[] res = new int[i];//i号位存储该位置所需要最少的操作数（追踪记录）
res[0]=0;
res[1]=2;
res[2]=3;
//找规律（推出递推方程）
//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
//规律同一计算的因子步骤数一致
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){
//是因子 除不尽全部单个黏贴和因子的最小操作数方式对比
minOpr=Math.min(minOpr,y+res[x/y-1]);
}
}
}
res[x-1]=minOpr;
}
return res[i-1];
}
