井字格不重复最多走法

墨蓝 2023-01-01 07:57 156阅读 0赞

### 题目： ###

*  从起点（0,0）沿着边走到终点（m,n），走的路不重复，求有多少种不同的走法？  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L211c3VueQ_size_16_color_FFFFFF_t_70]

### 算法设计 ###

*  方法一：利用递归思想，从终点（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 datetime
    
    
    class WellPath:
        count = 0
    
        def paths(self, m, n):
            if m == 0 and n == 0:
                return 1
            if m < 0 or n < 0:
                return 0
            self.count += 1
            return 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 - start
        print(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 datetime
    
    
    class WellPath:
        count = 0
        cache = [[0 for i in range(100)] for j in range(100)]
    
        def paths(self, m, n):
            if m == 0 and n == 0:
                return 1
            if m < 0 or n < 0:
                return 0
            self.count += 1
            if 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] = temp
            return temp
    
    
    if __name__ == '__main__':
        well_path = WellPath()
        start = datetime.datetime.now()
        result = well_path.paths(14, 14)
        end = datetime.datetime.now()
        delta = end - start
        print(f'paths: {result},recurse count:{well_path.count},time:{delta.seconds}.{delta.microseconds} s')

输出结果：

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L211c3VueQ_size_16_color_FFFFFF_t_70]: /images/20221120/bcad74d9924d440f8b0cb3cd88bbd01e.png