代码随想录训练营第34天|dp前置转移

62. 不同路径

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n,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];}
};

dp[i][j]:运动至(i,j)的方案数

转移方程：可由上/左两个方向转移而来，累加不同的方案数。

63. 不同路径 II

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int row=obstacleGrid.size();int col=obstacleGrid[0].size();vector<vector<int>> dp(row, vector<int>(col,0));for(int j=0; j<col&&obstacleGrid[0][j]==0; j++)dp[0][j]=1;for(int i=0; i<row&&obstacleGrid[i][0]==0; i++)dp[i][0]=1;for(int i=1; i<row; i++){for(int j=1; j<col; j++){if(obstacleGrid[i][j]==0){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}}return dp[row-1][col-1];}
};

dp[i][j]:运动至(i,j)的方案数

转移方程：

• 没有障碍物的情况下，可以由上或左两个方向转移而来；
• 有障碍物的情况只能取0，表示没有方案，不可达。

343. 整数拆分

class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1,0);dp[2]=1;for(int i=3; i<=n; i++){for(int j=1; j<i; j++){dp[i]=max({dp[i],dp[i-j]*j,(i-j)*j});}}return dp[n];}
};

dp[i]：拆分i可以达到的最大乘积

转移方程：给定i，可能由任何一个前置的j拆分而来，对于剩下的部分（i-j）由两种选择：

• 1.不拆，此时拆分乘积为 （i-j)*j
• 2.拆，此时拆分乘积为 dp[i-j]*j

根据dp的定义对二者取最大。

另外，dp[1]初始化为0，表示拆分1的情况是非法的，这样取max后自然被过滤掉。

96. 不同的二叉搜索树

class Solution {
public:int numTrees(int n) {vector<int> dp(n+1,0);dp[0]=1;for(int i=1; i<=n; i++){for(int j=1; j<=i; j++){dp[i]+=dp[j-1]*dp[i-j];}}return dp[n];}
};

dp[i]：给定节点数i，可构造的搜索树数目

转移方程：给定节点数i，搜索树的根可以取前置任一节点：1、2……i，dp[i]累加不同情况而来。选定j（j<=i）作为根：

• 左子树节点数为：j-1，左子树的形态数目：dp[j-1]。
• 右子树节点数为：i-(j+1)+1，形态数：dp[i-j]，不需要关注每个节点具体数值的差异。
• 根据乘法原理，由左右子树个数得到整个树的形态数：dp[j-1]*dp[i-j]。