Dynamic Programming - Easy Level - Question 1

Dynamic Programming - Easy Level - Question 1

Leetcode 1646 Get Maximum in Generated Array

You are given an integer n. An array nums of length n + 1 is generated in the following way:

nums[0] = 0

nums[1] = 1

nums[2 * i] = nums[i] when 2 <= 2 * i <= n

nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n

Return the maximum integer in the array nums​​​.

Constraints:

0 <= n <= 100

Analysis:

This question is quick straightforward: the state and transitional formula are given; the initialization is also given. So we can just ready the code to iterate all the states and find the maximum.

See the code below:

class Solution {
public:
    int getMaximumGenerated(int n) {
        int res = 0;
        if(n<2) return n;
        vector<int> f(n+1, 0);
        f[1] = 1;
        for(int i=2; i<=n; ++i) {
            if(i&1) f[i] = f[i/2] + f[i/2+1];
            else f[i] = f[i/2];
            // cout<<i<<" "<<f[i]<<endl;
            res = max(res, f[i]);
        }
        return res;
    }
};

Upper Layer