企业官网建设流程全解析

法（一）DFS——超时

路径问题，一上来就想到BFS，逻辑是对的，但是m和n比较大的时候会超时。

whatever，再熟悉一下，递归的思路。

首先，不是一上来就想到递归，递归只是一种手动，应该先想到深度优先搜索的思想，然后用递归实现DFS。

先画图，画着画着就出来了俩信息：

• 一个节点分裂出俩节点，说明待会dfs里面要自调用两次
• 递归出口有两个，一个是到了终点，一个是数组越界

class Solution { int count; public int uniquePaths(int m, int n) { dfs(0,0,m,n); return count; } public void dfs(int x, int y,int m, int n){ //递归出口1：越界 if(x<0 || x>=m ||y<0 ||y>=n) return; //递归出口2: 到达终点 if(x==m-1&&y==n-1){ count++; return; } //分裂两个结点 dfs(x+1,y,m,n); dfs(x,y+1,m,n); } }

法（二）二维动态规划

这个题刚看到的时候，我对于“只能往右、往下走”就有些疑惑，DFS明明能处理上下左右都能走的，怎么莫名其妙给简化了呢？但是没来得及细想就去写DFS了。

如果是上下左右都能走的话，那只能递归。但是题目限定了只能往右、往下走，一下子就能想到可以初始化二维数组的第一行和第一列。

• 定义递推问题dp[i][j]：到达{x,y}的最多路径
• 地推关系：dp[i][j]=dp[i-1][j]+dp[i][j-1]

class Solution { public int uniquePaths(int m, int n) { int [][]dp = new int[m][n]; //初始化第一行 for(int j=0;j<n;j++){ dp[0][j]=1; } //初始化第一列 for(int i=0;i<m;i++){ dp[i][0]=1; } //无论是一行一行推还是一列一列推都可以，这里一行一行推 for(int i=1;i<m;i++){ for(int j=1; j<n; j++){ dp[i][j]=dp[i][j-1]+dp[i-1][j]; } } return dp[m-1][n-1]; } }