建设用地规划许可证去哪个网站查,万网网站建设教程,信息网站 cms,网站建设套餐介绍动态规划part03 343. 整数拆分解题思路 96.不同的二叉搜索树解题思路 343. 整数拆分 题目链接#xff1a; 343. 整数拆分 文章讲解#xff1a; 343. 整数拆分 视频讲解#xff1a; 343. 整数拆分 解题思路
动态规划五部曲
确定dp数组以及下标的含义 dp[i]#xff1a;分… 动态规划part03 343. 整数拆分解题思路 96.不同的二叉搜索树解题思路 343. 整数拆分 题目链接 343. 整数拆分 文章讲解 343. 整数拆分 视频讲解 343. 整数拆分 解题思路
动态规划五部曲
确定dp数组以及下标的含义 dp[i]分拆数字i可以得到的最大乘积为dp[i]。确定递推公式 j是从1开始遍历拆分j的情况在遍历j的过程中其实都计算过了。那么从1遍历j比较(i - j) * j和dp[i - j] * j 取最大的。递推公式dp[i] max(dp[i], max((i - j) * j, dp[i - j] * j)); 也可以这么理解j * (i - j) 是单纯的把整数拆分为两个数相乘而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。 如果定义dp[i - j] * dp[j] 也是默认将一个数强制拆成4份以及4份以上了。 所以递推公式dp[i] max({dp[i], (i - j) * j, dp[i - j] * j}); 那么在取最大值的时候为什么还要比较dp[i]呢 因为在递推公式推导的过程中每次计算dp[i]取最大的而已。dp初始化 初始化dp[2] 1遍历顺序 因为拆分一个数n 使之乘积最大那么一定是拆分成m个近似相同的子数相乘才是最大的。 只不过我们不知道m究竟是多少而已但可以明确的是m一定大于等于2既然m大于等于2也就是 最差也应该是拆成两个相同的 可能是最大值。 那么 j 遍历只需要遍历到 n/2 就可以推导dp数组
// 动态规划
class Solution {public int integerBreak(int n) {//dp[i] 为正整数 i 拆分后的结果的最大乘积int[] dp new int[n1];dp[2] 1;for(int i 3; i n; i){for(int j 1; j i / 2; j){dp[i] Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));// j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j 再相乘//而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。}}return dp[n];}
}96.不同的二叉搜索树 题目链接 96.不同的二叉搜索树 文章讲解 96.不同的二叉搜索树 视频讲解 96.不同的二叉搜索树 解题思路
确定dp数组dp table以及下标的含义 dp[i] 1到i为节点组成的二叉搜索树的个数为dp[i]。确定递推公式 dp[i] dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] j相当于是头结点的元素从1遍历到i为止。 所以递推公式dp[i] dp[j - 1] * dp[i - j]; j-1 为j为头结点左子树节点数量i-j 为以j为头结点右子树节点数量dp数组如何初始化 初始化dp[0]0确定遍历顺序举例推导dp数组
// 动态规划
class Solution {public int numTrees(int n) {int[] dp new int[n1];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];}
}
