云南seo整站优化报价,做网站用的是什么语言,乐陵属于山东哪个市,滨州网站建设公司报价动态规划#xff1a;05不同路径
62. 不同路径
五部曲 确定dp数组含义#xff1a;到达第i#xff0c;j位置的路径条数为d[i][j] 确定递归公式#xff1a;d[i][j]d[i-1][j]d[i][j-1] 我们发现#xff0c;想要到d[i][j]#xff0c;只能从d[i-1][j]或者d[i][j-1]达到 dp数…动态规划05不同路径
62. 不同路径
五部曲 确定dp数组含义到达第ij位置的路径条数为d[i][j] 确定递归公式d[i][j]d[i-1][j]d[i][j-1] 我们发现想要到d[i][j]只能从d[i-1][j]或者d[i][j-1]达到 dp数组初始化dp[0][j] 1,dp[i][0] 1 遍历顺序从左到右从上到下 我们的初始值是在最上面和最左面 debug打印dp数组
代码
class Solution {public int uniquePaths(int m, int n) {int[][] dp new int[m][n];//初始化for(int i 0; i m; i) dp[i][0] 1;for(int j 0; j n; j) dp[0][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]; }
}总结
本题还是使用动规五部曲但这次我们就要考虑如何正确的初始化了初始化和遍历顺序其实也很重要
