[数据结构与算法]每日一题-LeetCode获取生成数组中的最大值

1646. 获取生成数组中的最大值

动态规划：
定义dp[i] 表示nums[i]的值
dp 递推公式
当n>=2 ，

• 为偶数时候 nums[2 * i] = nums[i] ,两边下标都除以2，因为i为偶数，因此i/2 一定能整除，因此等价于 ==> a[i] = a[i/2];
• 为奇数的时候 nums[2 * i + 1] = nums[i] + nums[i + 1] ==> 两边下标同时处以2
  nums[i+1/2] = nums[i/2]+nums[(i+1)/2]
  因为int 类型所以 1/2 = 0

==> a[i] = a[i/2]+a[(i+1)/2]

初始条件
dp[0]=0;
dp[1]=1;
dp[2]=1;

public int getMaximumGenerated(int n) {
        if(n == 0){
            return 0;
        }
        if(n<=2){
            return 1;
        }
        int[] dp = new int[n+1];
        dp[0]=0;
        dp[1]=1;
        //走到这一步，说明n>2
        int max = 1;
        for(int i=2;i<=n;i++){
            if(i%2 ==0){
                dp[i] = dp[i/2];
            }else{
                dp[i] = dp[i/2]+dp[(i+1)/2];
            }
            max = Math.max(max,dp[i]);
        }
        return max;

    }