组合问题与动态规划的联系之应用
一，问题描述
假设有个机器人坐在 X×Y 网格的最左上角，每次只能向下或者向左移动。最左上角的坐标标记为(0,0)，最右下角的坐标为(X,Y)
请问：机器人从(0,0)走到(X,Y)共有多少种走法？其实这个问题与 这篇文章 中提到的问题非常相似。
二，问题分析
这个问题一共有三种方式来求解。第一种是使用公式；第二种是使用递归；第三种是使用动态规划
使用递归和动态规划，其实本质上是一致的。都是使用组合原理进行问题分析。
机器人从(0,0)走到(X,Y)一共需要走 X+Y步。其中必须有X步是向下走的(因为最终的横坐标是X)。问题转化为：从X+Y步走法中，选出X步是向下走，一共有多少种选法?这是一个组合问题了。答案是C(X+Y,X)
还有另一种理解方式：
由于机器人不能往回走，只能向下或者向左走。因此，将向下走记为 Down，向左走记为Left。问题就转化为{X·Down, Y·Left}的一个全排列问题。
即：集合{X·Down, Y·Left}有两个元素，Down和Left。Down一共有X个，Left一共有Y个。
从(0,0)走到(X,Y)就相当于对集合所有的元素进行全排列。由于这是一个“重集合”，故全排列数为 (X+Y)!/X!·Y!
其中，(X+Y)!/X!·Y! 等于 C(X+Y,X)
对于(X,Y)，一共有两种情况：从(X-1,Y)向下走一步到达(X,Y)；从(X,Y-1)向右走一步到达(X,Y)
设steps(X,Y)表示从(0,0)走到(X,Y)一共用的方式数，那么 steps(X,Y)=steps(X-1,Y)+steps(X,Y-1)
初始条件：steps(0,0)=1；steps(x,0)=steps(0,y)=1
因此，就可以代表上面的公式使用递归或者DP求解了。
三，代码实现
public class Steps { public static int steps(int x, int y) { if(x < 0 || y < 0) throw new IllegalArgumentException(); return steps_recur(x, y); } //使用递归来求解 private static int steps_recur(int x, int y) { assert x >=0 || y >= 0; if(x == 0 || y == 0) return 1; return steps_recur(x - 1, y) + steps_recur(x, y - 1); } //dp resolve public static int steps_dp(int x, int y) { if(x < 0 || y < 0) throw new IllegalArgumentException(); int[][] dp = new int[x + 1][y + 1]; //dp的初始条件 for(int i = 0; i <= x; i++) dp[i][0] = 1;//y==0，说明只能向右走 for(int i = 0; i <= y; i++) dp[0][i] = 1;//x==0，说明只能往下走 //状态方程的实现,for循环从1开始,充分体现了自底向上的思想 for(int i = 1; i <= x; i++) { for(int j = 1; j <= y; j++) { dp[i][j] = dp[i-1][j] + dp[i][j - 1]; } } return dp[x][y]; } //使用公式来求解 public static int steps_factorial(int x, int y){ if(x < 0 || y < 0) throw new IllegalArgumentException(); return factorial(x + y) / (factorial(x) * factorial(y)); } //求n! public static int factorial(int n){ if(n < 0) throw new IllegalArgumentException(); int res = 1; for(int i = 1; i <= n; i++) res *= i; return res;//0!=1 } //test public static void main(String[] args) { int x = 1; int y = 5; System.out.println("dp solve:" + steps_dp(x, y)); System.out.println("formula solve:" + steps_factorial(x, y)); System.out.println("recursive solve:" + steps(x, y)); } }
四，参考资料
优质内容筛选与推荐>>1、[deviceone开发]-土地销售App开源
2、(原)tslib的交叉编译
3、请问utf-8的中文是一个汉字占三个字节长度吗？
4、My publication and Paper Review
5、2019-2019-2-20175332-实验三《敏捷开发与XP实践》实验报告