如何优化用于计算数组最大美观度的递归代码？

给定一个整数数组，你可以删除任意数量的元素，返回数组的最大美观度。美观度的定义是：最终数组中，元素值与其所在位置（位置从1开始）相等的元素个数。

示例：数组arr = [1,3,3]的美观度为2，因为最终数组[1,3,3]中，位置1的元素1、位置3的元素3均满足条件。

你提供的递归代码存在以下核心问题：

1. 数组按值传递：每次递归都会拷贝整个vector<int>，造成大量时间和空间浪费
2. 递归分支逻辑错误：最后一行的递归调用未处理「删除当前元素」的分支（应将rem加1），反而重复计算了「不删除当前元素」的情况，导致无法得到正确结果
3. 无记忆化机制：存在大量重复子问题（相同的i和rem组合），时间复杂度为指数级，处理较大数组时会超时

原代码错误分支示例：

// 错误：未处理删除当前元素的情况，rem应+1
ans = max(ans, rec(arr, i+1, n, rem, curCount));

方案1：修复递归逻辑+引用传递+记忆化搜索 #

先修正递归分支，加入记忆化缓存避免重复计算，同时将数组改为引用传递以减少拷贝开销：

优化后的递归代码 #

#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>

using namespace std;

// 记忆化缓存：用"i,rem"字符串作为键，存储对应状态的最大美观度
unordered_map<string, int> memo;

int rec(const vector<int>& arr, int i, int n, int rem) {
    // 递归终止：处理完所有元素
    if (i == n) {
        return 0;
    }
    
    // 检查缓存，避免重复计算
    string key = to_string(i) + "," + to_string(rem);
    if (memo.find(key) != memo.end()) {
        return memo[key];
    }
    
    int max_count = 0;
    // 分支1：不删除当前元素
    int current_pos = i - rem + 1; // 当前元素保留后的1-based位置
    if (arr[i] == current_pos) {
        // 当前元素符合条件，计数+1，继续处理下一个元素
        max_count = max(max_count, 1 + rec(arr, i+1, n, rem));
    } else {
        // 当前元素不符合条件，计数不变
        max_count = max(max_count, rec(arr, i+1, n, rem));
    }
    
    // 分支2：删除当前元素，已删除数量+1，计数不变
    max_count = max(max_count, rec(arr, i+1, n, rem + 1));
    
    // 将结果存入缓存
    memo[key] = max_count;
    return max_count;
}

// 调用入口
int maxBeauty(vector<int>& arr) {
    memo.clear(); // 每次调用清空缓存
    return rec(arr, 0, arr.size(), 0);
}

优化点说明 #

• 引用传递数组：const vector<int>& arr避免递归时的数组拷贝，大幅提升效率
• 记忆化缓存：缓存(i, rem)状态对应的最大美观度，将时间复杂度从指数级降至O(n²)
• 修正分支逻辑：明确区分「不删除当前元素」和「删除当前元素」两个分支，确保逻辑正确性

方案2：动态规划（迭代式） #

将递归转化为迭代式动态规划，避免递归栈开销，同时保持时间复杂度O(n²)：

动态规划代码 #

#include <vector>
#include <algorithm>

using namespace std;

int maxBeauty(vector<int>& arr) {
    int n = arr.size();
    // dp[i][j]：处理前i个元素，删除j个元素时的最大美观度
    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= i; ++j) {
            // 情况1：不删除第i个元素（原数组索引为i-1）
            if (j <= i-1) {
                int current_pos = i - j; // 保留后的1-based位置
                if (arr[i-1] == current_pos) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j] + 1);
                } else {
                    dp[i][j] = max(dp[i][j], dp[i-1][j]);
                }
            }
            // 情况2：删除第i个元素，已删除数量+1
            if (j >= 1) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]);
            }
        }
    }
    
    // 遍历所有可能的删除数量，取最大值
    int max_val = 0;
    for (int j = 0; j <= n; ++j) {
        max_val = max(max_val, dp[n][j]);
    }
    return max_val;
}

优化点说明 #

• 迭代式实现避免递归栈溢出风险，运行更稳定
• 空间复杂度为O(n²)，可进一步优化为O(n)（仅保留上一行状态）

方案3：空间优化的动态规划 #

通过滚动数组将空间复杂度降至O(n)：

#include <vector>
#include <algorithm>

using namespace std;

int maxBeauty(vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n+1, 0);
    
    for (int i = 1; i <= n; ++i) {
        // 从后往前遍历，避免覆盖未使用的状态
        for (int j = i; j >= 0; --j) {
            if (j <= i-1) {
                int current_pos = i - j;
                if (arr[i-1] == current_pos) {
                    dp[j] = max(dp[j], dp[j] + 1);
                }
                // 不满足条件时dp[j]保持不变，无需处理
            }
            if (j >= 1) {
                dp[j] = max(dp[j], dp[j-1]);
            }
        }
    }
    
    int max_val = 0;
    for (int val : dp) {
        max_val = max(max_val, val);
    }
    return max_val;
}

内容的提问来源于stack exchange，提问作者Nithya N