井字格不重复最多走法

题目：

• 从起点（0,0）沿着边走到终点（m,n），走的路不重复，求有多少种不同的走法？
  

算法设计

• 方法一：利用递归思想，从终点（m,n）来看，能走到终点的走法有多少种，假设paths(m,n)表示从起点走到（m,n）的走法数量，那么有表达式：paths(m,n)=paths(m,n-1)+paths(m-1,n)。含义是，到达（m,n）点的走法等于到达(m,n-1)的走法加上到达(m-1,n)的走法，只有这两个途径可以到达(m,n)。
• 方法二：动态规划，待补充

算法实现

• 方法一：递归算法

public class WellPath {public static long count = 0;/*** 递归算法* paths(m,n)=paths(m-1,n)+paths(m,n-1)* 特殊点m=n=0，m<0,n<0*/public static long paths(int m, int n) {if (m == 0 && n == 0) {return 1;}if (m < 0 || n < 0) {return 0;}count++;return paths(m - 1, n) + paths(m, n - 1);}public static void main(String[] args) {long start = System.nanoTime();long result = WellPath.paths(14, 14);long end = System.nanoTime();System.out.printf("paths: %s,recurse count:%d,time:%d (microsecond)", result, count, (end - start) / 1000);}
}

输出结果：

paths: 40116600,recurse count:115000919,time:445815 (microsecond)

import datetimeclass WellPath:count = 0def paths(self, m, n):if m == 0 and n == 0:return 1if m < 0 or n < 0:return 0self.count += 1return self.paths(m - 1, n) + self.paths(m, n - 1)if __name__ == '__main__':well_path = WellPath()start = datetime.datetime.now()result = well_path.paths(14, 14)end = datetime.datetime.now()delta = end - startprint(f'paths: {result},recurse count:{well_path.count},time:{delta.seconds}.{delta.microseconds} s')

输出结果：

paths: 40116600,recurse count:115000919,time:62.990346 s

• 优点：递归算法简单易懂，实现起来也快

• 缺点：样例数据过大，会导致递归调用次数过多，性能低

• 改进：由于在计算paths(m-1,n)时用了paths(m-2,n)+paths(m-1,n-1),计算paths(m,n-1)时用了paths(m-1,n-1)+paths(m,n-2)，可以观察出，paths(m-1,n-1)被使用了两次，在计算paths(m-1,n-1)是重复进行了递归计算，这里将之前计算好的paths(m-1,n-1)缓存起来，下次计算需要使用时，就从缓存取，这样减少递归次数。

• 方法一改进版：引入缓存

public class WellPath {public static long count = 0;public static long[][] cache = new long[100][100];/*** 递归算法* paths(m,n)=paths(m-1,n)+paths(m,n-1)* 特殊点m=n=0，m<0,n<0*/public static long paths(int m, int n) {if (m == 0 && n == 0) {return 1;}if (m < 0 || n < 0) {return 0;}count++;if (cache[m][n] > 0) {return cache[m][n];}long result = paths(m - 1, n) + paths(m, n - 1);cache[m][n] = result;return result;}public static void main(String[] args) {long start = System.currentTimeMillis();long result = WellPath.paths(14, 14);long end = System.currentTimeMillis();System.out.printf("paths: %s,recurse count:%d,time:%d", result, count, (end - start));}
}

输出结果:

paths: 40116600,recurse count:419,time:43 (microsecond)

import datetimeclass WellPath:count = 0cache = [[0 for i in range(100)] for j in range(100)]def paths(self, m, n):if m == 0 and n == 0:return 1if m < 0 or n < 0:return 0self.count += 1if self.cache[m][n] > 0:return self.cache[m][n]temp = self.paths(m - 1, n) + self.paths(m, n - 1)self.cache[m][n] = tempreturn tempif __name__ == '__main__':well_path = WellPath()start = datetime.datetime.now()result = well_path.paths(14, 14)end = datetime.datetime.now()delta = end - startprint(f'paths: {result},recurse count:{well_path.count},time:{delta.seconds}.{delta.microseconds} s')

输出结果：

paths: 40116600,recurse count:419,time:0.998 s