일일 버클:62.다양한 경로, 3가지 방법, 동적 기획 효율 최고

package com.sample.suncht.algo;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 62.     
 * 

 *           m x n        （          “Start” ）。
 * 

 *                  。             （       “Finish”）。
 * 

 *             ？
 *
 * @author sunchangtan
 * @date 2019/3/14 09:38
 */
public class UniquePaths {
    private HashMap 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> 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);
    }
}