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] = 1 i = 1时,只有一个结点①组成二叉搜索树,只有一个结点,只有一种摆放方式,故,dp[1] = 1. i = 2时,有两个结点①和②可以组成二叉搜索树,所以我们有两种思路 ①作为根结点,记为j,左边有j-1个元素比它小,右边有i - j个元素比它大 ②作为根结点同理。 而它的左右子树,有几个元素呢,你会发现一定比当前的i值小。都不大于2. 那么它们各有几种摆放方式呢?前面的dp数组构造时,已经考虑过了i = 0时,dp[0]=1, i=1时,dp[1]=1.两个相乘,就是以j为根的i个元素可以构造的二叉搜索树数量。最后将所有不同根结点情况相加即可。
暴力求解的思想,就是利用回溯算法,不撞南墙不回头。 但是如果我们预先将其存储到dp数组,就可以直接通过dp, 获取数据,而不用枚举。典型的动态规划题目
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数组输出看看,是否和自己预想的一样。)
class Solution { public int numTrees ( int n) { int dp[ ] = new int [ n+ 1 ] ; dp[ 0 ] = dp[ 1 ] = 1 ; for ( int i = 2 ; i<= n; i++ ) { for ( int j = 1 ; j<= i; j++ ) { dp[ i] += dp[ j- 1 ] * dp[ i- j] ; } } return dp[ n] ; }
}