本文主要是介绍代码随想录day39| 62.不同路径 ,63. 不同路径 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
62. 不同路径
dp[i][j]:到达这个数组不同路径和
递推公式：dp[i][j] = dp[i-1][j]+dp[i][j-1] ——因为题目中要求是只可以向下或者向左
初始化：dp[i][0]和dp[0] 都是为1——因为只可以向下或者向左走，这两边只能直走
遍历顺序：从前向后，从上到下
int **initDP(int m, int n){int **dp = (int**)malloc(sizeof(int*)*m);int i , j;for(i = 0; i < m; ++i){dp[i] = (int*)malloc(sizeof(int)*n);}for(i = 0; i < m; ++i){dp[i][0] = 1;}for(j = 0; j < n; j++){dp[0][j] = 1;}return dp;
}
int uniquePaths(int m, int n) {int **dp = initDP(m, n);int i, j;for(i = 1; i < m; ++i){for(j = 1; j < n; ++j){dp[i][j] = dp[i-1][j] + dp[i][j-1];}}int result = dp[m-1][n-1];free(dp);return result;
}63. 不同路径 II
dp[i][j]:到达这个数组不同路径和
递推公式：没有路障的时候 dp[i][j] = dp[i-1][j]+dp[i][j-1] ——因为题目中要求是只可以向下或者向左
初始化：两边上遇到障碍后变成初始化零，在其前面初始化为1
遍历顺序：从上到下，从左到右
int **intiDP(int m, int n, int** obstacleGrid){int **dp = (int**)malloc(sizeof(int*) * m);int i, j;for(i = 0; i < m; ++i){dp[i] = (int*)malloc(sizeof(int) * n);}for(i = 0; i < m; ++i)dp[i][0] = 0;for(j = 0; j < n; ++j){dp[0][j] = 0;}for(i = 0; i < m; ++i){if(obstacleGrid[i][0])break;dp[i][0] = 1;}for(j = 0; j < n; ++j){if(obstacleGrid[0][j])break;dp[0][j] = 1;}return dp;
}
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize) {int m = obstacleGridSize, n = *obstacleGridColSize;int **dp = intiDP(m, n, obstacleGrid);int i, j;for(i = 1; i < m; ++i){for(j = 1; j < n; ++j){if(obstacleGrid[i][j])dp[i][j] = 0;elsedp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];
}这篇关于代码随想录day39| 62.不同路径 ,63. 不同路径 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
