package dynamic;

/**题目:求路径数量
 * 给定一个m*n的矩阵
 * 要求计算从左上角走到右下角一共的走法,要求就是只能向右和向下走
 * @Author Gavin
 * @date 2022年01月09日 16:15
 */
public class solution_6 {
 /**
 * 动态规划题目:
 * 需要找到状态和状态方程
 * 我们知道一个m*n的矩阵的左上角到第0行的右边任何列的走法只有一种,
 * 到第0列上面的任何行的走法也只有一种
 * 所以可以得出如下的状态方程:
 * d(0,j)=1
 * d(i,0)=1
 * d(i,j)=d(i-1,j)+d(i,j-1)
 */
 public int solution(int m,int n){
 if(m<1||n<1)return 0;
 //定义一个二维数组用来存遍历值
 int[][] d=new int[m][n];
 //先填充第0行和第0列的初始值为1
 for (int i = 0; i < n; i++) {
 d[0][i]=1;
 }
 for (int i = 0; i < m; i++) {
 d[i][0]=1;
 }
 for (int i = 1; i < m; i++) {
 for (int j = 1; j < n; j++) {
 d[i][j]=d[i-1][j]+d[i][j-1];
 }
 }
 return d[m-1][n-1];
 }
}