牛牛组数题解

题解：根据题意可以进行递归模拟，此方法最为简便，不过当n大于500时，会造成堆栈溢出或时间复杂度过高等问题。
递归的代码参考如下：

int f(int n){
    if(n == 1) return 1;
    int result = 0;
    for(int i = 1; i <= n/2; ++i)  
        result += f(i);
    return result + 1;  
}

所以考虑递推的做法，先举例来演算，以4为例
可以组成14,24,124,4
可以推得
f[1]=1
f[2]=2=f[1]+1
f[3]=2=f[1]+1
f[4]=4=f[1]+f[2]+1
f[5]=4=f[1]+f[2]+1
以此类推，参考代码如下

long long solve(int n)
{
    // write code here
    long long f[10001] = {0};
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i / 2; j++)
        {
            f[i] += f[j];
        }
        f[i]++;
    }
    return f[n];
}

不过时间复杂度为n^2
可以在此基础上继续优化，参考代码如下
时间复杂度O(n),空间复杂度O(n)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最多满足条件的组法
     * @param n int整型 
     * @return long长整型
     */
    long long solve(int n) {
        // write code here
        long long f[10005] = {0};
        long long sum[5005] = {0};

        f[1] = 1;
        for (int i = 2; i <= n; ++i)
        {
            sum[i / 2] = sum[i / 2 - 1] + f[i / 2];
            f[i] = sum[i / 2] + 1;
        }
        return f[n];
    }
};