现在流行做网站吗,常平众展做网站,蓝色响应式机械类网站,wordpress自定义文章模板输入#xff1a;两个int m和n 输出#xff1a;一个int,表示不同路径的个数。 规则#xff1a;有一个m行n列的矩阵#xff0c;一个机器人从左上角走到右下角#xff0c;每次向下或者向右走一格。 分析#xff1a;目的是要找到从(0,0)到(m-1,n-1)有多少种不同 的走法。如果…输入两个int m和n 输出一个int,表示不同路径的个数。 规则有一个m行n列的矩阵一个机器人从左上角走到右下角每次向下或者向右走一格。 分析目的是要找到从(0,0)到(m-1,n-1)有多少种不同 的走法。如果m3n2。我们按照下图走一遍。知道有3种走法。先观察每种走法向下的箭头都是2个向右的箭头都是1个。所以可以得出结论无论哪种走法向右和向下的数量是一定的。向下的数量是m-1向右的数量是n-1。从(0,0)到(m-1,n-1)要经过mn-2步。所以这就是一个组合题Cmn−2m−1C^{m-1}_{mn-2}Cmn−2m−1。 public int uniquePaths(int m, int n) {int a Math.min(m,n)-1;int b mn-2;long p 1;long q 1;for(int i0;ia;i){p p * (b-i);q q * (i1);}return (int)(p/q);}分析2我们给这个矩阵每个方格用坐标表示(i,j)。 我们用dp[i][j]表示走到坐标(i,j)有多少种走法。 我们自己手画一下知道dp[1][1]2就是有2种路径到达(1,1)。看图中能够到达(1,1)只有可能是从(1,0)或者(0,1)这两个坐标走过来。那dp[1][1]与dp[1][0]、dp[0][1]是什么关系呢 实际走一下知道dp[0][1]1dp[1][0]1那么dp[1][1]dp[1][0]dp[0][1]。为了防止错误再多走几个格子:dp[2][0]1,dp[2][1]dp[2][0]dp[1][1]。从含义角度讲经过(0,1)点达到(1,1)和经过(1,0)点到达(1,1)的路径肯定是不相同的所以用加法不会出错也不会计算重复了。所以得到动态方程 dp[i][j]dp[i−1][j]dp[i][j−1]dp[i][j]dp[i-1][j]dp[i][j-1]dp[i][j]dp[i−1][j]dp[i][j−1] 第0行和第0列的数据需要单独初始化。 public int uniquePaths(int m, int n) {int[][] dp new int[m][n];dp[0][0] 1;for(int j1;jn;j){dp[0][j]1;}for(int i1;im;i){dp[i][0] 1;}for(int i1;im;i){for(int j1;jn;j){dp[i][j] dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];}空间优化 public int uniquePaths(int m, int n) {int[] dp new int[n];for(int j0;jn;j){dp[j]1;}for(int i1;im;i){for(int j1;jn;j){dp[j] dp[j]dp[j-1];}}return dp[n-1];}参考链接
