Joker0806 level
获赞
6
粉丝
0
关注
6
看过 TA
25
五邑大学
2023
Java
IP属地:广东
暂未填写个人简介
私信
关注
头像
2023-03-06 17:30
Java
今天完成了动态规划专项-线性dp的DP1-9。DP1、DP2其实都是很简单的斐波那契数列,DP3开始的话就发生了变化,从原来的每一次只能上1级或2级,到现在DP3每一次可以上n级,其实DP3如果找到规律的话就可以发现递推公式为dp(n)=2^(n - 1)。DP4(最小花费爬楼梯),也是每一次只能上1级或2级,但是要计算支付的费用,需要花费最少的费用达到顶端,递推公式为dp(n)=Math.min(dp(n - 1) + cost[n - 1],dp(n - 2) + cost[n - 2])。DP5(有多少不同的二叉搜索树),从1到n的n个节点,有多少种不同的方法去构建二叉搜索树。这道题我认为比较重要的点在于能否理解构建过程,比如1-10这10个节点,当根节点为1或10时,这时只有右子树或左子树(特殊情况);当以i为根节点的时候,左子树有1~i-1(i-1个节点),右子树有i+1~n(n-i个节点),那么递推公式则为dp(n)=sum(dp(i - 1)*dp(n - i))。DP6(连续子数组最大和)还是相对比较简单,只需要处理好每个元素和前面元素的大小就行。DP7(连续子数组的最大乘积)需要对数组进行正负处理,dpMax存储最大值,dpMin存储最小值,dpMax和dpMin的递推公式分别为dpMax[i]=Math.max(dpMax[i - 1] * nums[i],Math.max(dpMin[i - 1] * nums[i],nums[i]))和dpMin[i]=Math.min(dpMax[i - 1] * nums[i],Math.min(dpMin[i - 1] * nums[i],nums[i]))。DP8(乘积为正数的最长连续子数组)和DP9(环形数组的连续子数组最大和)还不是很理解,需要重复复习。
2023-03-06
在牛客打卡1天,今天学习:刷题 10 道/代码提交 19 次
0 点赞 评论 收藏
转发
牛客网
牛客企业服务