动态规划面试题--数字转化机

最近编程题目都是DP，我把今天这个题给大家做个解释和实现。大家好好体会练习，遇到最优解问题(最小/最大)时，优先DP解法。

概念

一般求最优解通常使用DP(Dynamic Programming)。

DP主要两个要素，有三种解法。

• 两要素
  • 定义状态
  • 定义状态转化方程

状态和状态转化方程最关键也比较困难。状态转化方程包含边界。有时称为三要素，是把边界单独分离出来，与状态和状态转化方程并列。

• 三种解法
  • 递归法
    递归法是直接使用状态转化方程，实际算不上DP，而是减而治之，在重叠子问题时，效率低下（时间复杂度O(2^n)）。
  • 备忘录法
    备忘录法实际上是对递归法优化，通过增加存储空间保存中间运算值，减少递归运算次数。
  • 表格法
    这是最正统的DP，递归法和备忘录法都是自顶而下的递归，表格法是自底而上的迭代。DP本质是把递归变为迭代，降低时间复杂度。

---

题目

时间限制：(每个case)2s，空间限制：128MB
小Q从牛博士那里获得一台数字转化机，这台数字转化机必须同时输入两个整数a和b，并且这台数字转化机有一个红色按钮和一个蓝色按钮。

• 当按下红色按钮，两个数字同时加一。
• 当按下蓝色按钮，两个数字同时乘二。

小Q现在手中有四个整数，a、b、A和B，他希望将输入的两个整数a、b变成A、B（a对应A，b对应B）。因为牛博士允许小Q使用数字转化机时间有限，所以，小Q希望按动按钮的次数越少越好，请你帮帮小Q吧。

• 输入：
  输入包括一行，一行中包含四个整数a,b,A,B。（1<=a,b,A,B<=10^9)
• 输出：
  如果小Q能够完成转换，输出最少需要按动按钮的次数，否则输出-1。
• 样例输入：

100 1000 202 2002

• 样例输出：

2

---

分析

• 定义状态
  transfer(first,last)表示从数字first转化到数字last最少转化次数
• 定义状态转移方程
  自顶而下分析，最后一步转化无非两种情况，前一步结果*2或者+1，那么前一次结果为last/2或者last-1。最后一步经历的转化次数无非是transfer(first,last/2)或者transfer(first,last-1)。显然可得，取最小的transfer(first,last) = min(transfer(first,last/2),transfer(first,last-1))+1
  递归边界最终会有两种情况，一种是first刚好与last相同，说明这是可以转换。一种是first>last，说明不能完成转化。
  结合上面两点状态转移方程如下所示：
  

解决

为了使代码更加简洁地表示解决思路，中间未添加参数检查处理。

测试主函数

本题测试函数非常简单只是终端输入输出操作。

int main(){
    int a(0),b(0),A(0),B(0);
    cin >> a >> b >> A >> B;
    int res1 = transfer(a,A);
    int res2 = transfer(b,B);
    if(res1 == res2 and -1 != res1){
        cout << res1;
    }else{
        cout << -1;
    }
}

实现转换函数transfer()

• 递归法
  直接把状态转换函数翻译成代码即可。

int transfer(int first,int last){
    if(first == last) return 0; // 可以完成转换
    if(first > last) return -1; // 不能完成转换
    int res1 = transfer(first,last/2);
    int res2 = transfer(first,last-1);
    if(-1 == res1 and -1 == res2){
        return -1;
    }else if(-1 == res1){
        return res2+1;
    }else if(-1 == res2){
        return res1+1;
    }else{
        return min(res1,res2)+1;
    }
}

注意，转化失败的分支不能参与最小转化次数比较的。程序需要增加这些处理。

• 备忘录法
  在递归过程中，记录计算结果，下次出现时不需要重新计算，直接从存储结果中获取即可。

int transfer(int first,int last,int buf[]){
    if(first == last) return 0; // 可以完成转换
    if(first > last) return -1; // 不能完成转换
    if(-1 != buf[last]){
        return buf[last];
    }
    int res1 = transfer(first,last/2,buf);
    int res2 = transfer(first,last-1,buf);
    if(-1 == res1 and -1 == res2){
        return -1;
    }else if(-1 == res1){
        buf[last] = res2+1;
    }else if(-1 == res2){
        buf[last] = res1+1;
    }else{
        buf[last] = min(res1,res2)+1;
    }
    return buf[last];
}
int transfer(int first,int last){
    int buf[last+1];
    fill_n(buf,last+1,-1);
    return transfer(first,last,buf);
}

注意这里定义一个数组，数组的下标表示last，数组值表示从数字first转化到数字last最少转化次数。数组需要初始化为无效值-1，用于判断是否已经计算过。

• 表格法
  表格法用自底而上的迭代代替自顶而下的递归。

int transfer(int first,int last){
    int buf[last+1];
    fill_n(buf,last+1,0);
    for(int i=first+1;i<=last;i++){
        if(i/2 >= first and i-1 >= first){
            buf[i] = min(buf[i/2],buf[i-1])+1;
        }else if(i/2 >= first){
            buf[i] = buf[i/2]+1;
        }else if(i-1 >= first){
            buf[i] = buf[i-1]+1;
        }else{
            buf[i] = -1;
        }
    }
    return buf[last];
}

这里数组表示含义与备忘录法一致的，虽然会有一定空间浪费，时间复杂度，已经从O(2^n)降低到O(n)。

通常有时间限制的DP，优先使用表格法，备忘录法在一些情况会比表格法快，基本不使用递归法。

使用回溯法可以把表格法和备忘录法获得的存储中间值，转化成获得最优解具体的操作，例如本题中，小Q究竟是依次按了哪些按钮获得last值。有能力的童鞋，可以自己练习解决。