锚文本对网站,如何安装网站程序,单页网站建设哪里有提供,山西网络营销外包文章目录 动态规划理论基础动规五部曲#xff1a;出现结果不正确#xff1a; 343. 整数拆分96.不同的二叉搜索树 动态规划理论基础
动规五部曲#xff1a;
确定dp数组 下标及dp[i] 的含义。递推公式#xff1a;比如斐波那契数列 dp[i] dp[i-1] dp[i-2]。初始化dp数组。… 文章目录 动态规划理论基础动规五部曲出现结果不正确 343. 整数拆分96.不同的二叉搜索树 动态规划理论基础
动规五部曲
确定dp数组 下标及dp[i] 的含义。递推公式比如斐波那契数列 dp[i] dp[i-1] dp[i-2]。初始化dp数组。确定遍历顺序从前到后or其他。推导dp数组。
出现结果不正确
打印dp日志和自己想的一样递推公式、初始化或者遍历顺序出错。打印dp日志和自己想的不一样代码实现细节出现问题。
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五部曲
dp[i]含义第i个数可以拆分的两个正整数的乘积的最大化。递推公式dp[i] max(dp[i], dp[j]*dp[i-j]); 除了2与3之外的计算方式可以将正整数从2开始拆分为两个正整数获得乘积的最大值为两个 正整数最大 的成绩之和。由于是选择所以选择max进行选取。而n2返回的1n3返回的2单独将正整数拆分含有2和3时表示的是2和3而不是1和2。初始化if(n 2) return 1; else dp[2] 2; if(n3) return 2; else dp[3] 3;遍历顺序从小到大。推导dp数组n 5。 dp {0, 1, 1, 2, 4, 6}。
代码
class Solution {
public:int integerBreak(int n) {vectorint dp(n1, 0);if(n 2) return 1;dp[2] 2;if(n3) return 2;dp[3] 3;for(int i 4; i n; i){for(int j 2; j i; j){dp[i] max(dp[i], dp[j]*dp[i-j]);}}return dp[n];}
};96.不同的二叉搜索树 参考文档代码随想录 题目
分析
dp五部曲
dp[i]含义表示 i个节点 构成不同二叉树的个数 dp[i]。递推公式根据三个节点可以构成二叉树的个数可以得知dp[i] dp[j] * dp[i-j-1]; j 从0到i。初始化0个节点可以构成的二叉树有一个所以dp[0] 1。遍历顺序从小到大。推导dp数组n 3 dp [1,1,2,5]。
代码
class Solution {
public:int numTrees(int n) {//n3时。 0-21-12-0j, i-j-1vectorint dp(n1);dp[0] 1;for(int i 1; i n; i){for(int j 0; j i; j){dp[i] dp[j] * dp[i-j-1];}}return dp[n];}
};
