DFS与DP两种实现方式

1.DP方法：
dp[i][j] = dp[i-1][j]+dp[i][j-1]
压缩空间表示
dp[i]= dp[i-1]+dp[i]
初始化dp[0~n]=1; 因为当m=1时所有路径为1。

 public int uniquePaths (int m, int n) {
        // write code he
        int[] dp = new int[n];
        for(int i=0;i<n;i++) dp[i]=1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[j] = dp[j-1]+dp[j];
            }
        }
        return dp[n-1];
    }
}

2.记忆化+DFS:

import java.util.*;
public class Solution {
    /**
     *
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public int res =0;
    public HashMap<Integer,HashMap<Integer,Integer>> map;
    public int uniquePaths (int m, int n) {
        // write code he
        boolean[][] vis = new boolean[m][n];
        this.map = new HashMap();
        vis[0][0] = true;
        DFS(0,0,m,n,vis);
        return res;
    }
    public int DFS(int x, int y,int m,int n,boolean[][] vis){
        int[][] dis = {{1,0},{0,1}};
        int cnt=0;
        if(x==m-1&&y==n-1){
            res++;
            return 1;
        }
        if(x>=m||x<0||y>=n||y<0) return 0;
        if(map.containsKey(x)&& map.get(x).containsKey(y)){
            cnt= map.get(x).get(y);
            res+=cnt;
            return cnt;
        }
        for(int i=0;i<2;i++){
            int xx= x+dis[i][0];
            int yy = y+dis[i][1];
            if(xx>=0&&xx<m&&yy>=0&&yy<n&&vis[xx][yy]==false){
                vis[xx][yy] = true;
                cnt+=DFS(xx,yy,m,n,vis);
                vis[xx][yy] = false;
            }
        }
        if(!map.containsKey(x)) map.put(x,new HashMap());
        this.map.get(x).put(y,cnt);
        return cnt;

    }
}