long f(int n) //n是正整数 { if (n<5) return n; long prod=0; for (i=1; i<n; i++) prod = max{prod, f(i)*(n-i)}; return prod; } （1）写出求f(n)的递归模型，并分析该算法的时间复杂度。 （2）写一个改进算法，降低时间复杂度。

（1）递归模型如下：

当n小于5时，f(n)的值为n。

当n大于等于5时，f(n)的值等于max{f(i) * (n-i)}，其中i的取值范围为[1, n-1]。

该算法的时间复杂度为O(n^n)，因为在计算f(n)的过程中，需要计算f(1)、f(2)、...、f(n-1)，而每次计算f(i)时，都需要计算f(1)、f(2)、...、f(i-1)，因此会有很多重复计算。

（2）改进算法如下：

使用一个数组来保存已经计算过的f值，避免重复计算。

从小到大依次计算f(1)、f(2)、...、f(n)，每次计算f(i)时，只需要考虑i之前的f值，不需要再次计算之前的f值。

时间复杂度为O(n^2)，因为只需要计算n个f值，每个f值的计算只需要O(n)的时间。改进后的代码如下：

long f(int n, vector<long>& memo) {
    if (n < 5) return n;
    if (memo[n] != 0) return memo[n];
    long prod = 0;
    for (int i = 1; i < n; i++) {
        prod = max(prod, f(i, memo) * (n - i));
    }
    memo[n] = prod;
    return prod;
}

long f(int n) {
    vector<long> memo(n + 1, 0);
    return f(n, memo);
}