每日力扣：62. 不同路径，3种方式，动态规划效率最高

超、凢脫俗 2022-03-08 04:04 408阅读 0赞

package com.sample.suncht.algo;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    
    /**
     * 62. 不同路径
     * <p>
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
     * <p>
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
     * <p>
     * 问总共有多少条不同的路径？
     *
     * @author sunchangtan
     * @date 2019/3/14 09:38
     */
    public class UniquePaths {
        private HashMap<ValueEntity, Integer> valueMap = new HashMap<>();
    
        /**
         * 纯递归
         * 执行用时: 直接超时
         * @param m
         * @param n
         * @return
         */
        public int uniquePaths0(int m, int n) {
            if (m < 1 && n < 1) {
                return 0;
            }
    
            if (m == 1 || n == 1) {
                return 1;
            }
    
            return this.uniquePaths0(m - 1, n) + this.uniquePaths0(m, n -1);
        }
    
        /**
         * 递归 + 缓存（以避免重复计算）
         * 执行用时:169 ms	内存消耗:49.4 MB
         * @param m
         * @param n
         * @return
         */
        public int uniquePaths1(int m, int n) {
            if (m < 1 && n < 1) {
                return 0;
            }
    
            if (m == 1 || n == 1) {
                return 1;
            }
    
            int uniquePaths1 = 0;
            ValueEntity value1 = new ValueEntity(m - 1, n);
            if(valueMap.containsKey(value1)) {
                uniquePaths1 = valueMap.get(value1);
            } else {
                uniquePaths1 = this.uniquePaths1(m - 1, n);
                valueMap.put(value1, uniquePaths1);
            }
    
            int uniquePaths2 = 0;
            ValueEntity value2 = new ValueEntity(m, n -1);
            if(valueMap.containsKey(value2)) {
                uniquePaths2 = valueMap.get(value2);
            } else {
                uniquePaths2 = this.uniquePaths1(m, n -1);
                valueMap.put(value2, uniquePaths2);
            }
    
            return uniquePaths1 + uniquePaths2;
        }
    
        /**
         * 动态规划，效率最高
         * 执行用时: 0 ms	内存消耗:31.7 MB
         * @param m
         * @param n
         * @return
         */
        public int uniquePaths2(int m, int n) {
            if (m < 1 && n < 1) {
                return 0;
            }
    
            if (m == 1 || n == 1) {
                return 1;
            }
    
            int[][] matrix = new int[m][n];
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 1;
            }
    
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 1;
            }
    
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    matrix[i][j] = matrix[i - 1][j] + matrix[i][j-1];
                }
            }
    
            return matrix[m-1][n-1];
        }
    
        public static class ValueEntity {
            private final int m;
            private final int n;
    
            public ValueEntity(int m, int n) {
                this.m = m;
                this.n = n;
            }
    
            @Override
            public int hashCode() {
                return String.format("%d:%d", m, n).hashCode();
            }
    
            @Override
            public boolean equals(Object obj) {
                if(this == obj) {
                    return true;
                }
    
                if(!(obj instanceof ValueEntity)) {
                    return false;
                }
    
                ValueEntity that = (ValueEntity)obj;
                String str1 = String.format("%d:%d", m, n);
                String str2 = String.format("%d:%d", that.getM(), that.getN());
                return str1.equals(str2);
            }
    
            public int getM() {
                return m;
            }
    
    
            public int getN() {
                return n;
            }
    
            @Override
            public String toString() {
                return m + ", " + n;
            }
        }
    
        public static void main(String[] args) {
            List<AlgoHelper.BiInputParams<Integer, Integer, Integer>> datas = new ArrayList<>();
            datas.add(new AlgoHelper.BiInputParams<>(3, 2, 3));
            datas.add(new AlgoHelper.BiInputParams<>(7, 3, 28));
            AlgoHelper.assertResult(datas, new UniquePaths()::uniquePaths2);
        }
    }