package leecode.dynamic_programming;
/**
* @author: 老张爱吃西蓝花
* @description: https://leetcode-cn.com/problems/unique-paths/
* @date: 2020/10/21 11:07
*/
public class q_62 {
public static void main(String[] args) {
System.out.println(solutions(45,4));
}
public static int solutions(int m, int n) {
//找到边界条件和特殊情况
if (m == 0 || n == 0){
return m + n;
}
//定义DP数组
int[][] dp = new int[m][n];
//结合上面的特殊情况，可以看出单m/n==0时，只需要直接向下或向右，因此直接置上边界、左边界得值为 i
// - 当n为0时
for (int i = 0; i < m; i ++){
dp[i][0] = 1;
}
// - 当m为0时
for (int j = 0; j < n; j ++){
dp[0][j] = 1;
}
//找到DP数组元素关系式, 在这里:dp[i][j]=x代表了走了[i,j]这个位置需要x步
//而走到[i,j]这个位置, 有2种方法: 从[i-1][j]向右一步; 从[i][j-1]向下一步
//因此数组转移(状态关系)就找到了: dp[i][j] = dp[i-1][j] + dp[i][j-1]
for (int i = 1; i < m; i ++){
for (int j = 1; j < n; j ++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
