最近编程题目都是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值。有能力的童鞋，可以自己练习解决。
