63

题目

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

img

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

img

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

示例 2：

img

  • 输入：obstacleGrid = [[0,1],[0,0]]
  • 输出：1

提示：

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100

思路

本题其实就是将上一题的代码照搬过来 ，然后加上一个限制条件， 给了一个障碍物， 碰到障碍物就必须另寻它路。 当然题中没有排除左上角 和 右下角是否有障碍物的情况， 所以我们还需要做判断。

按照卡哥的动态规划五部曲的思路来进行解题

  1. 确定dp的含义

dp[i][j]: 表示 从（0，0） 到 （i，j） 一共有dp[i][j] 个方法

这是可以根据题意和按照对动态规划的掌握 来进行推导的。 如果刚开始没有接触过动态规划 ，那么还是需要按照卡哥的《代码随想录》系统的学习一下。

  1. 确定动归的递推公式

因为规定了只能向右或者向下走 ，所以dp[i][j] 可以是通过dp[i-1][j]和 dp[i][j-1]相加推导出来的

所以： dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

  1. 初始化

本题的初始化算是非常友好的了 ，从(0,0) 开始 ，同时他只能向右或者向下走 。所以初始化可以是

1
2
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即可。 也就是不需要做处理 ，因为有障碍物说明这条路已经行不通了 。

  1. 确定遍历顺序

从(0,0) 到(i,j) ，就需要使用两层for 循环将其挨个遍历 ，如果遇到obstacleGrid[i][j] == 1的情况 ，直接continue即可。

  1. 打印结果。（这个可有可无）

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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]))

所以按照顺序就可以进行遍历得到最大乘积。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 为节点组成的二叉搜索树有多少种？

示例:

img

思路

本题刚开始我并没有想到用动态规划能够怎么想出思路。 也是看了题解之后才理解的。 一开始我认为需要构建好二叉搜索树才能看出有什么规律， 但是写了几个之后并没有什么发现， 索性就战术性后退了。

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）作为右边的数量， 然后按照上面推出来的规律进行解就可以了

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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];
    }
}