一、问题描述
给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums :
- nums[0] = 0
- nums[1] = 1
- 当 2 <= 2 * i <= n 时,nums[2 * i] = nums[i]
- 当 2 <= 2 * i + 1 <= n 时,nums[2 * i + 1] = nums[i] + nums[i + 1]
返回生成数组 nums 中的 最大 值。
题目链接:获取生成数组中的最大值
二、题目要求
样例
输入:n=7输出:3解释:根据规则:nums[0] =0nums[1] =1nums[(1*2) =2] =nums[1] =1nums[(1*2) +1=3] =nums[1] +nums[2] =1+1=2nums[(2*2) =4] =nums[2] =1nums[(2*2) +1=5] =nums[2] +nums[3] =1+2=3nums[(3*2) =6] =nums[3] =2nums[(3*2) +1=7] =nums[3] +nums[4] =2+1=3因此,nums= [0,1,1,2,1,3,2,3],最大值3
考察
动态规划中等题型 建议用时15~30min
三、问题分析
还是用我们的三步走,老套路:
第一步 含义搞懂:
利用数字的奇偶性寻找性质,作为动态规划的切入口。
题目中dp[i]就代表第i个数字的值。
第二步 变量初始:
初始变量,原题描述给了,分别是:
dp[0]=0; dp[1]=1;
第三步 规律归纳:
题目虽然说2 * i、2*i+1的关系,我们反过来想,其实就是:
- 若 i 为偶数,dp[i]=dp[i/2];
- 若 i 为奇数,dp[i]=dp[i/2]+dp[i/2+1];
三步走,打完收工!
四、编码实现
classSolution { public: intgetMaximumGenerated(intn) { inti,dp[n+2],m;//初始化if(n==0) return0;//只有一个,返回0if(n==1) return1;//返回1dp[0]=0,dp[1]=1,m=1;//变量初始for(i=2;i<=n;i++) { if(i%2==0) { dp[i]=dp[i/2];//规律归纳 } elsedp[i]=dp[i/2]+dp[i/2+1];//规律归纳m=max(m,dp[i]); } returnm;输出结果 } };