动态规划之机器人行走问题
1. 问题描述：机器人一次可以走1m，2m或3m，那么机器人走n米有多少种走法？
2. 问题分析：
用a(n)来表示机器人走n米的走法总数，
那么，n<=0, a(n)=0;
n==1, a(n)=1;
n==2, a(n)=2: 1+1, 2;
n==3, a(n)=4: 1+1+1, 1+2, 2+1, 3;
但如此枚举下去不是办法，那么我们换个角度思考： 机器人走完全程的前一次运动时（注：机器人一次可以走1m，2m或3m），它离终点还有多远：
1. 还有1m, 进行一次走1m的运动就能到达终点。
2. 还有2m, 进行一次走2m的运动就能到达终点。
3. 还有3m, 进行一次走3m的运动就能到达终点。
这样一来的话，我们可以知道：a(n)=a(n-1)+a(n-2)+a(n+3), 即走n米的走法总数 = 走n-1米的走法总数 + 走n-2米的走法总数 + 走n-3米的走法总数
C语言实现：（动态规划——自底向上（迭代法））
// Hello, i'm 九院干干
/* ++++++++++++++++++++++++++++++++++++++++ + 关键点：a(n) = a(n-1) + a(n-2) + a(n-3) + 此版本借助了辅助n个空间，说明该算法还 + 可以进化 + 时间复杂度O(n), 空间复杂度O(n) ++++++++++++++++++++++++++++++++++++++++ */ #include <stdio.h> #include <stdlib.h> #define size 100 int RobotWalk(int n,int a[]) { int i,x; if(n<=0) return 0; if(n==1 ||n==2) return n; if(n==3) return 4; a[1] = 1; a[2] = 2; a[3] = 4; for(i=4; i<=n; i++) a[i] = a[i-1] + a[i-2] + a[i-3]; // 计算从小到大向前推进，计算a[4]->a[5]->...->a[n] return a[n]; } void main() { int n, KindSum; int a[size]; printf("请输入机器人要走的路程总长度："); scanf("%d",&n); KindSum = RobotWalk(n,a); printf("机器人的走法有%d种 ", KindSum); system("pause"); }
运行结果：
进一步优化：（上面的算法的空间复杂度为O(n)，改进后，只需3个辅助空间）
C语言实现：
/* +++++++++++++++++++++++++++++++++++++++++ + + 这个算法版本就是利用3个存储单元，存储计算米数 + 增加一个长度的三个历史走法总数。 + +++++++++++++++++++++++++++++++++++++++++ */ #include <stdio.h> #include <stdlib.h> int RobotWalk(int n) { int i, count, temp; int a[3] = {1,2,4}; if(n<=0) return 0; if(n==1) return a[0]; if(n==2) return a[1]; if(n==3) return a[2]; count= 0; /* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + +下面这个for循环是关键，count用来计数，以使数组a中每次只更新最老的历史数据， + 即最新的数据替换最老的数据，例如最先更新最老数据a[0]，a[0]成为最新数据；之后 + 更新最老数据a[1], a[1]成为最新数据；然后更新最老数据a[2]，a[2]成为最新数据。 + 此过程不断循环，直到计算出走n米的走法总数。 + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */ for(i=4; i<=n; i++) { temp = a[2] + a[1] + a[0]; a[count] = temp; count = (count+1)%3; //循环更新count，使其取值为{0,1,2}，对应于数组a的下标 } return temp; } void main() { int n, KindSum; printf("请输入机器人要走的路程总长度："); scanf("%d",&n); KindSum = RobotWalk(n); printf("机器人的走法有%d种 ", KindSum); system("pause"); }
运行结果：
除了运用自底向上的思维，当然还可以使用自顶向下的解法。
C语言实现：（动态规划——自顶向下（递归的方式））
// Hello, i'm 九院干干
/* +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + + 该算法是采用递归的思想，但需要记录计算过的子问题，以避免重复计算子问题。 + 因此，若是碰到曾经计算过得问题就直接返回其解。 + +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */ #include <stdio.h> #include <stdlib.h> #define size 1000 int RobotWalk(int n, int a[]) { if(a[n]!=0) return a[n]; //返回计算过的子问题的解 if(n<=0) return 0; if(n==1 || n==2) return n; if(n==3) return 4; else { a[n] = RobotWalk(n-1,a) + RobotWalk(n-2,a) + RobotWalk(n-3,a); // 递归实现 a[n] = a[n-1]+a[n-2]+a[n-3] return a[n]; } } void main() { int n, KindSum; int a[size] = {0}; //对数组元素初始化为0 printf("请输入机器人要走的路程总长度："); scanf("%d",&n); KindSum = RobotWalk(n,a); printf("机器人的走法有%d种 ", KindSum); system("pause"); }
运行结果：
Python实现：（自底向上 / 迭代法）：
# Hello, i'm 九院干干
#+++++++++++++++++++++++++++++++++++++++++++++++ # 此算法的辅助空间为3，则空间复杂度可以看成O(1) # 自底向上（迭代法） #++++++++++++++++++++++++++++++++++++++++++++++++ def RobotWalk(n): a= [1,2,4] if n<=0 : return 0 if n==1 or n==2 : return n if n==3 : return 4 else: count = 0 for i in range(4,n+1): temp = a[2] + a[1] +a[0] a[count] = temp count = (count+1)%3 return a[count-1] if __name__ == '__main__': n = int(input("请输入机器人要行走的总路程：")) KindSum = RobotWalk(n) print("机器人的走%d米的走法总数为：%d" %(n,KindSum))
运行结果：
Python实现：（动态规划——自顶向下（递归的方式））
def RobotWalk(n,a): if a[n]!=0 : return a[n] if n<=0: return 0 if n==1 or n==2: return n if n==3: return 4 else: for i in range(4,n+1): a[n] = RobotWalk(n-1,a) + RobotWalk(n-2,a) + RobotWalk(n-3,a) return a[n] if __name__ == '__main__': n = int(input("请输入机器人要行走的总路程：")) a = (n+1)*[0] KindSum = RobotWalk(n,a) print("机器人的走%d米的走法总数为：%d" %(n,KindSum))
运行结果：