记忆化搜索

#include <iostream>
#include <cstring> // 包含memset

using namespace std;

// 初始化记忆化数组，-1表示尚未计算过
int memo[10];

int countReachableApples(int apple_heights[], int index, int max_height_with_bench) {
    // 递归终止条件：所有苹果都检查完毕
    if (index == 10) {
        return 0;
    }

    // 如果已经计算过当前苹果的结果，则直接返回
    if (memo[index] != -1) {
        return memo[index];
    }

    // 当前苹果能被摘到
    if (apple_heights[index] <= max_height_with_bench) {
        memo[index] = 1 + countReachableApples(apple_heights, index + 1, max_height_with_bench);
    } else {
        // 当前苹果不能被摘到
        memo[index] = countReachableApples(apple_heights, index + 1, max_height_with_bench);
    }

    return memo[index];
}

int main() {
    int apple_heights[10];
    int max_reach_height;
    int bench_height = 30;

    // 读取10个苹果的高度
    for (int i = 0; i < 10; ++i) {
        cin >> apple_heights[i];
    }

    // 读取陶陶的最大伸手高度
    cin >> max_reach_height;

    // 计算陶陶站在板凳上后的最大可达高度
    int max_height_with_bench = max_reach_height + bench_height;

    // 初始化记忆化数组为-1
    memset(memo, -1, sizeof(memo));

    // 使用记忆化递归计算陶陶能够摘到的苹果数量
    int reachable_count = countReachableApples(apple_heights, 0, max_height_with_bench);

    // 输出结果
    cout << reachable_count << endl;

    return 0;
}