62.不同路徑

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

這道題和臺階題類似，到達下一個點是由上兩個點決定的，即該點左側的點和該點上面的點，到達該點的路徑總和為dp[i][j]=dp[i-1][j]+dp[i][j-1],dp數組初始化為整個二維數組的上邊界和左邊界，因為是從左上角出發，行進方向只有向右和向下，所以遍歷順序為從左到右從上到下，用兩層for從左到右一層一層遍歷，注意末尾點是dp[m-1][n-1]，不是dp[m][n]

63. 不同路徑 II

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

這道題是上一題的升級版，但是需要注意幾個前提條件，在初始化dp數組時，如果障礙物在最左和最上面邊界中，則初始化終止，保持為0，當從左到右從上到下遍歷dp數組時，遇到障礙物時，則dp[i][j]保持為0

343. 整數拆分

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

這道題代碼很簡潔，但思維很麻煩，dp[i]的含義是整數i拆分后乘積的最大值，遞推公式為dp[i]=max(dp[i]+max(j*(i-j),j*dp[i-j])),這個遞推公式意思是，dp[i]不斷更新其最大值，dp[i]的最大值由兩方面決定，一是拆分為兩個數，而是拆分為大于等于三個數以上的乘積，覆蓋所以可能拆分的情況，最后取其最大值。vector數組未初始化，默認全為0

96.不同的二叉搜索樹

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

dp數組的初始化只能初始化dp[0],其他dp數組值都是從零開始累加，如果有初值，就會增大，這道dp題利用了二叉搜索樹的特性，頂點的左子樹都是比它小的值，頂點的右子樹都是比它大的值，所以就很好判斷一個數，左右子樹的個數，而個數的排列方式能進行狀態轉移，用于下一層遞推，所以遞推公式為dp[i]+=dp[i-j]*dp[j-1]