做网站 框架,企业为什么需要网站,那个旅游网站做攻略最好,免费网站建设视频教程343. 整数拆分
1、确定dp数组以及下标含义。
dp[i]#xff1a;分拆数字i#xff0c;可以得到的最大的乘积
2、确定递推公式#xff1a;
dp[i]最大乘积出处#xff1a;从1遍历j到i#xff0c;j * dp[i-j] 与 j * (i-j)取最大值。( 拆分j的情况#xff0c;在遍历j的过程…343. 整数拆分
1、确定dp数组以及下标含义。
dp[i]分拆数字i可以得到的最大的乘积
2、确定递推公式
dp[i]最大乘积出处从1遍历j到ij * dp[i-j] 与 j * (i-j)取最大值。( 拆分j的情况在遍历j的过程中dp[i - j]其实都计算过了 )
所以递推公式为
dp[i] max(dp[i],max(j*(i-j),j*dp[i-j]));3、dp的初始化
dp[0] dp[1] 0;
dp[2] 1;
4、确定遍历顺序
由于递推公式dp[i]是依靠dp[i-j]的状态所以i遍历从前向后。j也是从前向后遍历的。
class Solution {
public:int integerBreak(int n) {vectorint dp(n1);dp[0] dp[1] 0;dp[2] 1;for(int i 1; i n; i){for(int j 1; j i; j){dp[i] max(dp[i],max(j*(i-j),j*dp[i-j]));}}return dp[n];}
};96. 不同的二叉搜索树
分析
dp[3] 元素1为头结点搜索树的数目 元素2为头结点搜索树的数目 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
所以 dp[3] dp[2] * dp[0] dp[1] * dp[1] dp[0] * dp[2];
1、确定dp数组以及下标含义
dp[i] : 1到i节点组成的二叉搜索树的个数
2、确定递推公式
dp[i] dp[j-1] * dp[i-j];
dp[j-1]:j为头结点左子树节点数量
dp[i-j]:i-j为头结点右子树节点数量3、dp数组初始化
dp[0] 1;
4、确定遍历顺序
从前往后遍历
for(int i 1; i n; i)
{for(int j 1; j i; j){dp[i] dp[j-1]*dp[i-j];}
}class Solution {
public:int numTrees(int n) {vectorint dp(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];}
};
