一、问题描述
给你一个整数 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;输出结果 } };
