动态规划-只有两个键的键盘

题目.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];
  }