网站建设咨询有客诚信,168电商平台,为网站做IPhone客户端,装修公司名字大全参考确定dp数组#xff08;dp table#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 62.不同路径 代码随想录 视频讲解#xff1a;动态规划中如何初始化很重要#xff01;| LeetCode#xff1a;62.不同路径_哔哩哔哩_bilibili class Solut… 确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 62.不同路径 代码随想录 视频讲解动态规划中如何初始化很重要| LeetCode62.不同路径_哔哩哔哩_bilibili class Solution {public int uniquePaths(int m, int n) {// 1.确定dp数组dp table以及下标的含义 : dp[i][j] 从[0][0]到[i][j]有多少种路径(是路径不是步数)// 2.确定递推公式 : dp[i][j]只能由这两个方向的路径推导出来dp[i - 1][j],dp[i][j - 1]// dp[i][j] dp[i - 1][j] dp[i][j - 1]// 3.dp数组如何初始化 : dp[0][j] 1; dp[i][0] 1; 画图只有一种路径// 4.确定遍历顺序 : 从左往右从上到下// 5.举例推导dp数组 :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];}
} 63. 不同路径 II https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.htmlhttps://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html 视频讲解动态规划这次遇到障碍了| LeetCode63. 不同路径 II_哔哩哔哩_bilibili class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int dp[][] new int[obstacleGrid.length][obstacleGrid[0].length];for (int i 0; i obstacleGrid.length obstacleGrid[i][0] 0; i) {dp[i][0] 1;}for (int j 0; j obstacleGrid[0].length obstacleGrid[0][j] 0; j) {dp[0][j] 1;}for (int i 1; i obstacleGrid.length; i) {for (int j 1; j obstacleGrid[0].length; j) {if (obstacleGrid[i][j] 0) {dp[i][j] dp[i - 1][j] dp[i][j - 1];}}}return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];}
}
