公司建设网站价格多少,市场营销计划,宁波制作网站知名,网站关键词分布题目链接#xff1a;力扣 解法一#xff1a;动态规划
定义状态#xff1a;对于m*n的网络#xff0c;从最后一行到右下角#xff0c;以及从最后一列到右下角#xff0c;都只有一条不同路径#xff1a;一直向右或一直向下#xff0c;所以可以定义状态#xff1a;dp[i][…题目链接力扣 解法一动态规划
定义状态对于m*n的网络从最后一行到右下角以及从最后一列到右下角都只有一条不同路径一直向右或一直向下所以可以定义状态dp[i][j]表示从 (i,j) 到右下角的不同路径数量初始状态和边界情况 根据状态的定义最后一行以及最后一列达到右下角的路径都只有一种所以初始状态为 dp[m-1][i] 1dp[i][n-1] 1确定状态转移现在最后一行和最后一列的状态已经确定其他的状态转移如下 根据状态的定义从 (i,j) 到达右下角有两种方案 往下走到达(i1j)这时dp[i][j] dp[i1][j]往右走到达(ij1)这时 dp[i][j] dp[i][j1]所以除以最下面一行以及最右边一列的其他状态转移方程为dp[i][j] dp[i1][j]dp[i][j1]
AC代码
class Solution {public static int uniquePaths(int m, int n) {int[][] dp new int[m][n];//赋初始值for (int i 0; i n; i) {dp[m - 1][i] 1;}for (int i 0; i m; i) {dp[i][n - 1] 1;}//状态转移for (int i m - 2; i 0; i--) {for (int j n - 2; j 0; j--) {dp[i][j]dp[i1][j]dp[i][j1];}}return dp[0][0];}
}
方法二排列组合因为从左上角到右下角一共会向下走m-1步向右走n-1步。总共需要移动mn-2步所以路径总数就是从这mn-2步中选择m-1次向下走的方案最终只需要求下面的公式值即可 分子一共右mn-2-n1m-1项分母一共有m-1项所以可以在一个for循环内通过连乘计算
AC代码
class Solution {public static int uniquePaths(int m, int n) {long result 1;for (int x n, y 1; y m; x, y) {result result * x / y;}return (int) result;}
}
