63
题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2 解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
思路
本题其实就是将上一题的代码照搬过来 ，然后加上一个限制条件， 给了一个障碍物， 碰到障碍物就必须另寻它路。 当然题中没有排除左上角 和 右下角是否有障碍物的情况， 所以我们还需要做判断。
按照卡哥的动态规划五部曲的思路来进行解题
确定dp的含义
dp[i][j]: 表示 从（0，0） 到 （i，j） 一共有dp[i][j] 个方法
这是可以根据题意和按照对动态规划的掌握 来进行推导的。 如果刚开始没有接触过动态规划 ，那么还是需要按照卡哥的《代码随想录》系统的学习一下。
确定动归的递推公式
因为规定了只能向右或者向下走 ，所以dp[i][j] 可以是通过dp[i-1][j]和 dp[i][j-1]相加推导出来的
所以： dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
初始化
本题的初始化算是非常友好的了 ，从(0,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;
将顺着向右 和 顺着向下的路都初始化成1 ， 因为只能一次走一格。 如果遇到obstacleGrid[0][j] == 1或者obstacleGrid[i][0] == 1的情况直接初始化成为 0即可。 也就是不需要做处理 ，因为有障碍物说明这条路已经行不通了 。
确定遍历顺序
从(0,0) 到(i,j) ，就需要使用两层for 循环将其挨个遍历 ，如果遇到obstacleGrid[i][j] == 1的情况 ，直接continue即可。
打印结果。（这个可有可无）
实现
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; //如果在起点或终点出现了障碍，直接返回0 if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) return 0; int [][]dp = new int[m][n]; 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; }else{ dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } } return dp[m-1][n-1]; } }
343
题目：
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
思路
先对题目进行拆分 ，dp[i] 可以定义为 对整数i 进行拆分 ，可以得到乘积最大，最大乘积为dp[i]
本题的拆分可以进行很多次， 要求最少是用两次， 我们这里可以使用另一个变量j
如果整数i 拆分得到的一个数为j 那么另一个就是i-j 他们的乘积就是j*(i-j) 。这样就是拆分成两个。 如果拆分为多个， 那么就是将(i-j) 再继续进行拆分。j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
所以得到的递推公式就是dp[i][j] = Math.max(dp[i][j], Math.max(j*(i-j), j*dp[i-j]))
所以按照顺序就可以进行遍历得到最大乘积。
实现
class Solution { public int integerBreak(int n) { int []dp =new int[n+1]; // 如果拆分为两个数 那么拆分乘积就是 j * (i-j) //如果拆分为更多的数， 那么拆分乘积就是 j * dp[i-j] // 我们需要做的就是找出拆分乘积最大的数 //初始化 dp[0] = 0; dp[1] = 0; dp[2] = 1; for(int i = 3;i <= n;i++){ for(int j = 1; j < i-1; j++){ dp[i] = Math.max(dp[i],Math.max(j*(i-j) , j*dp[i-j])); } } return dp[n]; } }
96
题目
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例:
思路
本题刚开始我并没有想到用动态规划能够怎么想出思路。 也是看了题解之后才理解的。 一开始我认为需要构建好二叉搜索树才能看出有什么规律， 但是写了几个之后并没有什么发现， 索性就战术性后退了。
n == 1的时候有1 个 n == 2 的时候 有 2 种， n == 3的 时候 有5 种….
代码随想录 (programmercarl.com)
之后的就是看卡哥题解了。
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]
之后 ，还是按照上一题的思路 ，用另一个变量 j 作为左边的数量，然后 （i-j）作为右边的数量， 然后按照上面推出来的规律进行解就可以了
实现
class Solution { public int numTrees(int n) { if(n ==1 && n ==2){ return n; } int []dp = new int[n+1]; dp[0] = 1; dp[1] = 1; // dp[3] = dp[0]*dp[3] + dp[1]*dp[2] + dp[3]* dp[0] for(int i = 2; i <= n;i++){ for(int j = 1; j <= i; j++){ dp[i] += dp[j-1]*dp[i-j]; } } return dp[n]; } }
