自己的网站怎么创建,网站音乐播放器代码,注册网址的网站,WordPress如何导入md文件96.不同的二叉搜索树
力扣题目链接(opens new window)
给定一个整数 n#xff0c;求以 1 ... n 为节点组成的二叉搜索树有多少种#xff1f; dp[3] dp[2] * dp[0] dp[1] * dp[1] dp[0] * dp[2] dp[i] #xff1a; 1到i为节点组成的二叉搜索树的个数为dp[i]。
dp[i] d…96.不同的二叉搜索树
力扣题目链接(opens new window)
给定一个整数 n求以 1 ... n 为节点组成的二叉搜索树有多少种 dp[3] dp[2] * dp[0] dp[1] * dp[1] dp[0] * dp[2] 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[0] 1,dp[1]能从dp0推出来所以不用初始化 实际上这道题应该这样理解对于数值是 n 的二叉搜索树的个数等于 以 1-n 的数值为头结点的个数相加。这一步相信大家都没啥问题。那么后面对于每一个头结点该怎样去算呢 举例n 为 7那么当头结点是 5 的时候将 1,2,3,4,6,7 这几个数字放进去根据二叉搜索树定义左子树小右子树大那么 1,2,3,4只能在左子树6,7在右子树中也就是说 左子树由四个数构成一颗二叉搜索树右子树有两个数构成一颗二叉搜索树这里右子树的 6,7 可以看成 1,2因为把头结点 5 不看的话1,2 构成的二叉搜索树和 6,7 构成的二叉搜索树的个数是一样的。这也是为什么只要布局相似即可。那么再看 方程 dp【i】 dp【j - 1】 * dp【i - j】把 i 7j 5 带入其实就是 dp【4】 * dp【2】 , 这里的 4 是个数2 也是个数。
class Solution {
public:int numTrees(int n) {vectorint dp(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];}
};动态规划01背包理论基础
本题力扣上没有原题大家可以去卡码网第46题 (opens new window)去练习题意是一样的。 dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。 递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
对应放入i物品 和不放入i物品 取价值大
初始化初始化第一行和第一列 剩下的随意初始化 因为剩下的每一个数都是通过这个数的上面的和左斜上方推出来的。 #include bits/stdc.h
using namespace std;int n, bagweight;// bagweight代表行李箱空间
void solve() {vectorint weight(n, 0); // 存储每件物品所占空间vectorint value(n, 0); // 存储每件物品价值for(int i 0; i n; i) {cin weight[i];}for(int j 0; j n; j) {cin value[j];}// dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值vectorvectorint dp(weight.size(), vectorint(bagweight 1, 0));// 初始化, 因为需要用到dp[i - 1]的值// j weight[0]已在上方被初始化为0// j weight[0]的值就初始化为value[0]for (int j weight[0]; j bagweight; j) {dp[0][j] value[0];}for(int i 1; i weight.size(); i) { // 遍历科研物品for(int j 0; j bagweight; j) { // 遍历行李箱容量// 如果装不下这个物品,那么就继承dp[i - 1][j]的值if (j weight[i]) dp[i][j] dp[i - 1][j];// 如果能装下,就将值更新为 不装这个物品的最大值 和 装这个物品的最大值 中的 最大值// 装这个物品的最大值由容量为j - weight[i]的包任意放入序号为[0, i - 1]的最大值 该物品的价值构成else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);}}cout dp[weight.size() - 1][bagweight] endl;
}int main() {while(cin n bagweight) {solve();}return 0;
}01背包理论基础滚动数组 在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。 递推式
不放物品i所背的背包最大价值还是dp【j】相当于从上一层的数组拷贝过来滚动
dp[j] max(dp[j], dp[j - weight[i]] value[i]);
dp[0]就应该是0因为背包容量为0所背的物品的最大价值就是0。 倒序遍历背包容量
因为二维数组是根据左上元素来求的一维数组自然就是靠左边来求的。倒序的时候左边元素再刷新前都是上一层的数据但正序就不一样了正序的时候左边的元素刚刚刷新过也就是左边的元素已经是本层的了意味着什么 这样会导致一个物品反复加好几次。
void test_1_wei_bag_problem() {vectorint weight {1, 3, 4};vectorint value {15, 20, 30};int bagWeight 4;// 初始化vectorint dp(bagWeight 1, 0);for(int i 0; i weight.size(); i) { // 遍历物品for(int j bagWeight; j weight[i]; j--) { // 遍历背包容量dp[j] max(dp[j], dp[j - weight[i]] value[i]);}}cout dp[bagWeight] endl;
}int main() {test_1_wei_bag_problem();
}jweight[i] 背包容量要大于本次刚入的物品
