- 62. 不同路径
- 思路
- 63. 不同路径 II
- 思路
- 343. 整数拆分
- dp思路
- 非dp思路
- 96. 不同的二叉搜索树
- 思路
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
示例 2：
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3 输出：28
示例 4：
输入：m = 3, n = 3 输出：6思路
首先应该确定dp[i]的含义：代表到达第 [i,j] 的位置有 dp[i][j]种方法。
确定递推公式: 因为到 [i,j] 位置可以从 [i-1, j] 位置向下走一步，也可以从 [i, j-1] 位置向右走一步，所以到到 [i,j] 位置的方法就是到 [i-1, j] 位置和第 [i, j-1] 位置的方法总和，即递推公式为：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
初始化：因为当 i = 0，时，只能从位置 [0, j-1] 到达位置 [0, j] ；当j = 0，时，只能从位置 [i-1, 0] 到达位置 [i, 0] ；所以dp[0,j] = 1, dp[i,0] = 1。
for (let i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (let j = 0; j < n; j++) {
dp[0][j] = 1;
}
确定循环顺序：到达当前位置的不同方法由到达左边和上边的方法的到，且行和列等于0时的方法已经初始化了，所以应该从1开始，从左至右，从上至下遍历。
确定返回值：因为题目求到达右下角有几种方法，所以返回 dp[m - 1][n - 1] 就好了。
一种写法
var uniquePaths = function(m, n) {
const dp = new Array(m).fill().map(() => new Array(n));
// 初始化
for (let i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (let i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
};
另一种写法
因为达当前位置的不同方法由到达左边和上边的方法得到，与当前位置原来的值没关系，所以可以在创建数组的时候就初始化。
var uniquePaths = function(m, n) {
const dp = new Array(m).fill().map(() => new Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
};
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]] 输出：1思路
这里dp数组的含义和递推公式与不同路径1是一样的，不同地方在于初始化和遍历的时候需要做一个判断。
初始化：因为当 i = 0，时，只能从位置 [0, j-1] 到达位置 [0, j] ；当j = 0，时，只能从位置 [i-1, 0] 到达位置 [i, 0] ；并且上诉两种情况中若中间有障碍物，那么后边的位置都无法到达，所以在创建数组的时候可以将所有元素都初始化为0,然后在单独初始化上诉两种情况dp[0,j] = 1, dp[i,0] = 1`。
for (let i = 0; i < m && obstacleGrid[i][0] != 1; i++) {
dp[i][0] = 1;
}
for (let i = 0; i < n && obstacleGrid[0][i] != 1; i++) {
dp[0][i] = 1;
}
确定循环顺序：到达当前位置的不同方法由到达左边和上边的方法的到，且行和列等于0时的方法已经初始化了，所以应该从1开始，从左至右，从上至下遍历，并且在遍历过程中若当前位置是障碍物那么当前位置无法到达，方法就为0。
var uniquePathsWithObstacles = function(obstacleGrid) {
let m = obstacleGrid.length;
let n = obstacleGrid[0].length;
const dp = new Array(m).fill().map(() => new Array(n).fill(0));
// 初始化
for (let i = 0; i < m && obstacleGrid[i][0] != 1; i++) {
dp[i][0] = 1;
}
for (let i = 0; i < n && obstacleGrid[0][i] != 1; i++) {
dp[0][i] = 1;
}
// 遍历
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
// 判断当前位置只有没有障碍物时才进行方法的统计
if (obstacleGrid[i][j] != 1)
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。dp思路
首先应该确定dp[i]的含义：代表 整数 i 拆分后的最大乘积为dp[i]。
确定递推公式：其实可以从1遍历 j，然后有两种渠道得到 dp[i]：一个是 j * (i - j) 直接相乘。一个是 j * dp[i - j]，相当于是拆分 (i - j)，对这个拆分不理解的话，可以回想dp数组的定义。可以这么理解 j * (i - j) 是单纯的把整数拆分为两个数相乘，而 j * dp[i - j] 是拆分成两个以及两个以上的个数相乘。 dp[i - j] * dp[j] 也是默认将一个数强制拆成4份以及4份以上了。
dp[i] = Math.max(dp[i], dp[i-j] * j, (i-j) * j);
初始化：严格从dp[i]的定义来说，dp[0] dp[1] 是没有意义的数值，所以只用初始化 dp[2] = 1, dp[3]级以后的值可以在遍历中得到不用初始化 。
dp[2] = 1;
确定循环顺序：dp[i] 由 dp[i - j]得到，所以遍历i一定是从左向右，先有dp[i - j]再有dp[i]。枚举j的时候，是从1开始的。i是从3开始，这样就可以由我们初始化的数值求出来其他的值。
确定返回值：因为题目求拆分整数n的最大乘积，所以根据dp数组的含义返回 dp[n] 就好了。
var integerBreak = function(n) {
const dp = Array(n + 1).fill(0);
// 初始化
dp[2] = 1;
for (let i = 3; i <= n; i++) {
for (let j = 1; j < i; j++) {
dp[i] = Math.max(dp[i], dp[i-j] * j, (i-j) * j);
}
}
return dp[n];
};
非dp思路
我们先列几个数找找规律（这里只是举例不保证积最大）：
4=2+2、5=3+2、6=3+3、7=3+2+2、8=2+2+2+2、9=3+3+3、10=2+2+2+2+2 …
观察可以得如下规律：
- 拆分的自然数不会超过3，因为4可以化为2+2，5可以化为3+2>5，所以所有的数都可以拆为只 有3和2的数；
- 因为都可以拆除3和2，所有为了使乘积大，应该先尽可能拆除3，而后拆除2，分成1无贡献；
考虑所有的n除以3的情况：
- 可以被3整除，那么就将他全部拆为3，如:9=3+3+3；
- 被3除余1，那么可以拆为形如3+3+……+3+4，即3+3+……+3+2+2，如10=3+3+2+2；
- 被3除余2，那么可以拆为形如3+3+……+3+2，如11=3+3+3+2；
var integerBreak = function(n) {
if (n <= 3) return n - 1;
// 统计最多能分成多少个3
let num = Math.floor(n / 3);
// 得到余数
let y = n % 3;
// 统计乘积
let ji = 1;
// 如果余数为1，则将余数赋值为4，3的数量减1
if (y === 1){
num--;
y = 4;
} else if (y === 0) {// 如果余数为0，则要将与数变为1,否则最后一步会使整个乘积变为0
y = 1;
}
// 循环求积
while(num--) {
ji *= 3;
}
// 最后乘以余数
ji *= y;
return ji;
};
96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1思路
首先应该确定dp[i]的含义：代表 i 个节点组成的互不相同的搜索树为dp[i]。
确定递推公式：分析一下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个元素的搜索树数量
for (let j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
初始化：严格从dp[i]的定义来说，空节点也是一棵二叉树，所以
dp[0] = 1;
确定循环顺序：dp[i] 由 i 之前的树的不同搜索树的种类得到，所以应该从左向右遍历。
确定返回值：因为题目求 n 个节点的不同二叉搜索树的个数，所以根据dp数组的含义返回 dp[n] 就好了。
var numTrees = function(n) {
const dp = new Array(n + 1).fill(0);
// 初始化
dp[0] = 1;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
};
