62. 不同路径
思路：思路挺好想的，dp数组表示到第i，j个位置的所有路径是多少，然后每个位置都由其左边和上边的格子而到，所以递归公式也出来了，遍历顺序就是从左往右，从上往下，最后返回右下角的dp[m-1][n-1]即可。
我的代码：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n,0));
for(int i=0;i<m;i++) {
dp[i][0]=1;
}
for(int i=0;i<n;i++) {
dp[0][i]=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
思路：这道题目有障碍，所以从初始化到遍历的过程都要考虑到障碍的存在。初始化的时候如果第一行或第一列中有碰到障碍物的时候，那么从这一格往右（往下）的所有格初始化也要随之为0，因为此路不通。遍历过程中，如果发现有障碍，那么这个循环就跳过，此时这个格子就为0，表示此路不通，最后同样返回右下角值即可。
我的代码：
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m=obstacleGrid.size();
int n=obstacleGrid[0].size();
if(obstacleGrid[m-1][n-1]==1||obstacleGrid[0][0]==1) return 0;
vector<vector<int>> dp(m,vector<int>(n,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) continue;
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
96. 不同的二叉搜索树
思路：这道题目挺难的，难在想到怎么取讨论所有的情况，n为1的时候有一棵树，n为2有两棵树，n为3的时候有五棵树。n为3的时候，有三种情况。当1为头结点的时候，其右子树有两个节点，和 n 为2的时候两棵树的布局是一样的。当3为头结点的时候，其左子树有两个节点，这两个节点的布局，和n为2的时候两棵树的布局也是一样的，当2为头结点的时候，其左右子树都只有一个节点，布局和n为1的时候只有一棵树的布局也是一样的。dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量。
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]。dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。递推公式：dp[i] += dp[j – 1] * dp[i – j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量。
这里提供我写的一个做题笔记：
我的代码：
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[j-1]*dp[i-j];
}
}
return dp[n];
}
};
今日总结
今天的这个二叉树题目也挺难的，看了卡哥讲解才理解。终于熬到周五了，不过这周末又是排满的一周，希望周末的时候能出一两篇ctf题解吧，加油！
