优化网站服务,搜索引擎快速排名推广,大网站有哪些,成都校园兼职网站建设一、动态规划DP
1、不同路径 62
首先是dp数组#xff0c;dp[i][j]表示从起点(0, 0)到达当前位置(i, j)的路径数#xff0c;转移方程从只能向下和向右移动可知#xff0c;初始化边界可直观推出第一行和第一列上的位置只有一条路径。
class Solution {
public:int uniquePa…一、动态规划DP
1、不同路径 62
首先是dp数组dp[i][j]表示从起点(0, 0)到达当前位置(i, j)的路径数转移方程从只能向下和向右移动可知初始化边界可直观推出第一行和第一列上的位置只有一条路径。
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint(n));// 初始化for(int i0; im; i)dp[i][0] 1;for(int i0; in; i)dp[0][i] 1;// 循环for(int i1; im; i)for(int j1; jn; j)dp[i][j] dp[i-1][j] dp[i][j-1];return dp[m-1][n-1];}
};空间复杂度优化采用一维数组来记录一行的状态通过循环来更新dp[i-1][j]的值。
class Solution {
public:int uniquePaths(int m, int n) {vectorint dp(n, 1);for(int i1; im; i)for(int j1; jn; j)dp[j] dp[j-1];return dp[n-1];}
};2、不同路径Ⅱ 63
这题相比于上一次只是多了障碍物的情况遇到障碍物则路径为0。
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size(), n obstacleGrid[0].size();vectorvectorint dp(m, vectorint(n));// 初始化for(int i0; im; i){if(obstacleGrid[i][0]0)dp[i][0] 1;elsebreak;}for(int i0; in; i){if(obstacleGrid[0][i]0)dp[0][i] 1;elsebreak;}// 循环for(int i1; im; i)for(int j1; jn; j)dp[i][j] (obstacleGrid[i][j]0? dp[i-1][j] dp[i][j-1] : 0);return dp[m-1][n-1];}
};同样的空间复杂度优化
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size(), n obstacleGrid[0].size();vectorint dp(n1);dp[1] (obstacleGrid[0][0]0);for(int i0; im; i)for(int j0; jn; j)dp[j1] (obstacleGrid[i][j]1 ? 0 : (dp[j]dp[j1]));return dp[n];}
};3、整数拆分 343
待更新… 4、不同的二叉搜索树 96
待更新… 二、写在后面
后续会出一期专门讲二维DP空间优化的博客敬请期待。
