62.不同路径

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

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

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

动态规划

dp[i][j]代表走到i,j时有几种走法。
(i,j)可以由(i-1,j)向下走得到，可以由(i,j-1)向右走得到。
所以dp[i][j]=dp[i-1][j]+dp[i][j-1]。
第一行和第一列的只有一种走法，那就是顺着一个方向一直走，所以他们都初始化为1。

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 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];
    }
}

数论方法（组合数）

地图是m*n，那么一共需要走m+n-2步，其中m-1步向下走，可以转换为组合问题，答案就是$C_{m+n}^{m-1}$。

63.不同路径II

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

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

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

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

有障碍的话，标记对应的dp[i][j]为0即可。

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1) {
                break;
            }
            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];
    }
}

343.整数拆分

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

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

示例 1:

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

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

1.动态规划，首先确定dp的含义。
dp[i]：拆分数字i可获得的最大乘积
2.确定递推公式
从i遍历j，有两种渠道得到dp[i]

• j*(j-i)直接相乘，相当于把i拆分为j，i-j
• dp[i-j]*j，相当于i-j已经拆分完了，再从i种拆分出j
• 还要比较dp[i]，因为会多次计算，取最大值。

3.初始化dp
dp[2]=1，因为2拆分为1+1，1*1=1
4.确定遍历顺序
dp[i]=max(dp[i],max((i-j)*j,dp[i-j]*j))
从前往后遍历

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i - 1; j++) {
            // 优化：j<=i/2，后面的没有必要遍历，一定不是最大值
                dp[i] = Math.max(Math.max(dp[i - j] * j, (i - j) * j), dp[i]);
            }
        }
        return dp[n];
    }
}

96.不同的二叉搜索树

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

首先找规律
n=1，一棵搜索树
n=2，两棵搜索树
n=3，五棵搜索树
n=3有几种情况：

• 1为根节点：两种
• 2为根节点：一种
• 3为根节点：两种

那么规律为：

• dp[3]：元素1为头节点搜索树的数量+元素2为头节点搜索树的数量+元素3为头节点搜索树的数量
• 元素1为头节点搜索树的数量=右子树有2个元素的搜索树数量+左子树0个元素的搜索树数量
• 元素2为头节点搜索树的数量=右子树有1个元素的搜索树数量+左子树1个元素的搜索树数量
• 元素3为头节点搜索树的数量=右子树有0个元素的搜索树数量+左子树1个元素的搜索树数量
• dp[3]=dp[2]*dp[0]+dp[1]*dp[1]+dp[0]*dp[2]
• 递推公式：dp[i]+=dp[j-1]*dp[i-j]，j-1为以j为头节点左子树节点数量，i-j为以j为头节点右子树节点数量。

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[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];
    }
}