题意：给定一个二维数组，找出从top left到bottom right的所有路径
思路：动态规划，遍历每一行，dp[i]表示某一行的节点i的所有可能路径总数，递推公式dp[i] = dp[左边的路径总数] + dp[上边的路径总数]
思想：动态规划
复杂度：时间O（m^n)，空间O(n)
class Solution {
public int uniquePaths(int m, int n) {
if(m == 0 || n ==0)
return 0;
int[] dp = new int[n];
for(int i=0;i<n;i++) {
dp[i] = 1;
}
for(int i=1;i<m;i++) {
for(int j=1;j<n;j++) {
dp[j] = dp[j] + dp[j-1];
}
}
return dp[n-1];
}
}
网友评论