网站管理系统改不了的,网站建设与维护百度百科,网站怎么做跳出提示筐,php做购物网站java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难#xff0c;但它就是固定套路而已。其实动态规划只…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难但它就是固定套路而已。其实动态规划只不过是将多余的步骤提前放到dp数组中就是一个数组只不过大家都叫它dp达到空间换时间的效果。它仅仅只是一种优化思路因此它目前的境地和线性代数一样----虚假的难。 想想线性代数在国外留学的学生大多数不觉得线性代数难理解。但是中国的学生学习线性代数时完全摸不着头脑一上来就是行列式和矩阵根本不知道这玩意是干嘛的。线性代数从根本上是在空间上研究向量抽象上研究线性关系的学科。人家国外的教科书都是第一讲就帮助大家理解研究向量和线性关系。反观国内的教材直接把行列式搞到第一章。搞的国内的学生在学习线性代数的时候只会觉得一知半解觉得麻烦完全不知道这玩意学来干什么。当苦尽甘来终于理解线性代数时干什么的时候发现人家国外的教材第一节就把这玩意讲清楚了。你只会大骂我们国内这些教材什么狗东西以上是自己学完线性代数后的吐槽我们同学无一例外都这么觉得。 而我想告诉你动态规划和线性代数一样我学完了才知道它不过就是研究空间换时间提前将固定的重复操作规划到dp数组中而不用暴力求解从而让效率极大提升。 但是网上教动态规划的兄弟们你直接给一个动态方程是怎么回事和线性代数一上来就教行列式和矩阵一样纯属恶心人。我差不多做了30多道动态规划题目才理解动态方程只是一个步骤而已而这已经浪费我很长时间了我每道题都一知半解不理解过程及其痛苦。最后只能重新做。动态规划一定是优先考虑重复操作与dp数组之间的关系搞清楚后再提出动态方程。而你们前面步骤省略了不讲一上来给个方程不是纯属扯淡吗我推荐研究动态规划题目按5个步骤从上到下依次来分析 DP数组及下标含义递推公式dp数组初始化数组遍历顺序双重循环及以上时才考虑dp数组打印分析思路是否正确相当于做完题检查一下 先理解题目细节 二叉搜索树左子树都比根结点小右子树都比根结点大左右子树又各是一个二叉搜索树。而如果给我们一个数3.那么也就是让我们用①、②、③这3个结点构成二叉搜索树。 如果我们用①作根结点那么②和③都大于①只能在它右边用②作根结点那么①小于②只能放在左边③大于②只能放在右边。那么左右分多少个结点呢我们发现当我们截取②作为根①、②、③这个序列它左边的都小于它所有最终都会在它左边同理右边的都在它右边。令j ②表示以②为根共有i 3个结点那么②左边的也就是j-1个 2-1 1个元素会被放在左子树。②右边的也就是i - j 3-2 1个元素会被放在右边 dp数组存储给你i个结点有几种摆放方式可以构成二叉搜索树。下标i表示当前给我们多少结点可以用于构成二叉搜索树。i 0时只有一种方法组成二叉搜索树就是什么都不摆故dp[0] 1i 1时只有一个结点①组成二叉搜索树只有一个结点只有一种摆放方式故dp[1] 1.i 2时有两个结点①和②可以组成二叉搜索树所以我们有两种思路 ①作为根结点记为j左边有j-1个元素比它小右边有i - j个元素比它大②作为根结点同理。 而它的左右子树有几个元素呢你会发现一定比当前的i值小。都不大于2. 那么它们各有几种摆放方式呢前面的dp数组构造时已经考虑过了i 0时dp[0]1, i1时dp[1]1.两个相乘就是以j为根的i个元素可以构造的二叉搜索树数量。最后将所有不同根结点情况相加即可。 解题思路 暴力求解的思想就是利用回溯算法不撞南墙不回头。但是如果我们预先将其存储到dp数组就可以直接通过dp, 获取数据而不用枚举。典型的动态规划题目 动态规划思考5步曲 DP数组及下标含义 我们要求出的是给你i个结点可以构造出多少种不同二叉搜索树。显然dp数组中存储的就是i个结点可以构造出多少种不同二叉搜索树。要求出谁的显然是求出i个结点可构造二叉搜索树数量。那么下标就是代表用几个结点构造二叉搜索树很显然只需要一个下标也就是一维数组。 递推公式 因为0个结点只有一种摆放方式1个结点也只有一种摆放方式所以F(0) F(1) 1;对于其它数i我们可以通过指定不同根结点构造多种不同二叉搜索树。我们用j来表示当前用哪个结点代表根结点。例如i 3有1,2,3这3个数可以构造当我们选其中一个数例如1.那么必须保证左边都小于它右边都大于它。也就是2和3必须在它右边而没有比1小的数因此左子树为空因此当我们选中j作为根结点后它左边有j-1个数右边有i-j个数。左边j-1个数可以构造dp[j-1]个不同二叉搜索树。右边i-j个数可以构造dp[i-j]个二叉搜索树。当我们j的右边固定不变时左边每变一次都是一课全新二叉搜索树。同理左边不变右边变也一样。所以他俩是相乘的关系。也就是以j为根节点有dp[j-1] * dp[i-j]种不同二叉搜索树。而当i 3我们有①②③这3个结点j可以选择任意一个作为根结点所以每种情况都得考虑因此j ① 和 j ② 和 j ③这3种情况的和才是dp[i]的值。故F[i] F[1-1] * F[i-1] F[2-1] * F[i-2] F[3-1] * F[i-3] … F[i-1] * F[i-i] dp数组初始化 数组遍历顺序(单重循环无需考虑遍历顺序一共就一维哪里来的谁先谁后)打印dp数组自己生成dp数组后将dp数组输出看看是否和自己预想的一样。 代码:时间复杂度O(n).空间复杂度O(n) class Solution {public int numTrees(int n) {int dp[] new int[n1];//需要0到n的下标范围因此需要n1个元素dp[0] dp[1] 1;//0个结点和1个结点只有一种摆放方式for(int i 2;in;i){//剩下的需要将不同结点作为根结点的情况加起来for(int j 1;ji;j){//j表示当前用谁当根结点dp[i]dp[j-1]*dp[i-j];//j当根结点左边有j-1个元素右边有i-j个元素}}return dp[n];//返回n个结点可以构成多少种二叉搜索树}
}
