【算法day27】动态规划：基础2

题目引用

不同路径
不同路径II
整数拆分
不同的二叉搜索树

1. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

我们还是五步走：
1.确定dp数组（dp table）以及下标的含义
到达当前位置共有多少种方法
2.确定递推公式
当我们到达当前位置时，只会是从上一个格子或者左一个格子过来的，其实就和昨天的题目差不多了。
dp[i][j]=dp[i-1][j]+dp[i][j-1]

3.dp数组的初始化
看到这道题目，其实我们是不难想到，当我们从起点一直往右走或者一直往下走都是只有1种方法的，因此我们就直接将dp数组的第0行和第0列赋值为1即可。
4.确定遍历顺序
这道题目就是从左到右、从上到下的顺序啦
5.举例推导dp数组

那么我们直接来看代码：

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 j=0;j<n;j++) dp[0][j]=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];}
};

2. 不同路径II

给定一个 m x n 的整数数组 grid。一个机器人初始位于左上角（即 grid[0][0]）。机器人尝试移动到右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含任何有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1.向右 -> 向右 -> 向下 -> 向下
2.向下 -> 向下 -> 向右 -> 向右

这题我们可以看到其实题目就是在过程中加入了障碍物这一概念，所以我们和上一题不同的地方就是初始化和遍历过程中如果遇到障碍物怎么解决的问题。初始化比较容易解决，遇到障碍物时我们可以想象到我们后面直接不赋值就好了，为什么，因为不可能找到方法再赋值了。
那么过程中的障碍物怎么解决呢，就是将遇到障碍物的位置不进行赋值，其他位置正常赋值，当遇到上面是障碍物时，我们只能从左边得到方法数，当遇到左边是障碍物时，只能从上边得到方法数。
来看代码吧：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m=obstacleGrid.size();int n=obstacleGrid[0].size();if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==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 j=0;j<n&&obstacleGrid[0][j]==0;j++) dp[0][j]=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];}
};

3. 整数拆分

给定一个正整数 n ，将其拆分为 k 个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。

返回你可以获得的最大乘积。

示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

还是那五步
1.确定dp数组（dp table）以及下标的含义
我们可以做一个类似于哈希表的映射，每一位的dp[i]都代表i能够拆分成的乘积最大数
2.确定递推公式
所以我们这里的dp[i]就很好推了，
dp[i]=max(dp[i],max((i-j)* j,dp[i-j] * j));
j是不大于i/2的值，我们利用循环嵌套将每一个可能的数进行比对而不产生重复判断，这样就可以得到dp[i]的乘积最大值。
3.dp数组的初始化
dp[2]=1
4.确定遍历顺序
我们这里还是从左到右
5.举例推导dp数组

那么来看代码吧

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(dp[i-j]*j,(i-j)*j));}}return dp[n];}
};

4. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

这道题目其实在咱们学习数据结构的时候就多多少少接触过了，我们先来思考一下n==3时为什么是五个
题目的示例可以很直观的体现这一点，当我们1打头时左0右2
当我们2打头时左1右1
当我们3打头时左2右0
我们再想想，我们树只有一个节点时，只有一种树，两个节点时，有两种树，那这个3个节点的时候是不是就是根据左右孩子的节点数不同来得到不同树的数量呢，1打头等于1乘2，2打头等于1乘1，3打头等于2乘1，再累加，就求出结果了，那么我们的状态表达式也就出来了：

for(int j=1;j<=i;j++){dp[i]+=dp[i-j]*dp[j-1];}

那么我们再初始化dp[0]，这题就出来了。
来看代码：

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];}
};