基于记忆化动态规划的打家劫舍问题实现求助：house数组填充错误

问题修正点 #

原代码仅计算了最大抢劫金额，但未正确回溯记录哪些房屋被抢劫，导致house数组标记错误，验证得分与返回金额不符。需在记忆化动态规划过程中记录每一步的选择，最后根据选择结果填充house数组。

修正后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int house[10000]; // 全局数组，标记房屋是否被抢劫（1=抢，0=不抢）

// 记忆化数组：存储从idx开始的最大金额
static int* memo;
// 选择记录数组：存储idx位置是否选择抢劫（1=抢，0=不抢）
static int* selected;

int rob_rec(int* nums, int idx, int numsSize) {
    if (idx >= numsSize) {
        return 0;
    }
    // 已计算过，直接返回记忆值
    if (memo[idx] != -1) {
        return memo[idx];
    }
    
    // 选项1：抢劫当前房屋，然后跳过下一间
    int rob_current = nums[idx] + rob_rec(nums, idx + 2, numsSize);
    // 选项2：不抢劫当前房屋，直接走下一间
    int skip_current = rob_rec(nums, idx + 1, numsSize);
    
    // 记录选择：选金额更大的选项
    if (rob_current > skip_current) {
        selected[idx] = 1;
        memo[idx] = rob_current;
    } else {
        selected[idx] = 0;
        memo[idx] = skip_current;
    }
    
    return memo[idx];
}

int rob(int* nums, int numsSize) {
    // 初始化全局house数组为0
    memset(house, 0, sizeof(house));
    if (numsSize == 0) {
        return 0;
    }
    
    // 分配记忆化和选择数组内存
    memo = (int*)malloc(sizeof(int) * numsSize);
    selected = (int*)malloc(sizeof(int) * numsSize);
    // 初始化记忆数组为-1（表示未计算）
    memset(memo, -1, sizeof(int) * numsSize);
    memset(selected, 0, sizeof(int) * numsSize);
    
    int max_amount = rob_rec(nums, 0, numsSize);
    
    // 根据selected数组回溯填充house数组
    int idx = 0;
    while (idx < numsSize) {
        if (selected[idx] == 1) {
            house[idx] = 1;
            idx += 2; // 抢了当前，跳过下一间
        } else {
            idx += 1; // 没抢，走下一间
        }
    }
    
    // 释放内存
    free(memo);
    free(selected);
    memo = NULL;
    selected = NULL;
    
    return max_amount;
}

// 以下是main函数，不可修改
int main() {
    // 测试用例1：nums = [1,2,3,1]，预期最大金额4，抢劫房屋0和2
    int nums1[] = {1,2,3,1};
    int size1 = sizeof(nums1)/sizeof(nums1[0]);
    int result1 = rob(nums1, size1);
    int verify1 = 0;
    for(int i=0; i<size1; i++){
        if(house[i]) verify1 += nums1[i];
    }
    printf("Test Case 1: Result = %d, Verify = %d\n", result1, verify1);
    
    // 测试用例2：nums = [2,7,9,3,1]，预期最大金额12，抢劫房屋0、2、4
    int nums2[] = {2,7,9,3,1};
    int size2 = sizeof(nums2)/sizeof(nums2[0]);
    int result2 = rob(nums2, size2);
    int verify2 = 0;
    for(int i=0; i<size2; i++){
        if(house[i]) verify2 += nums2[i];
    }
    printf("Test Case 2: Result = %d, Verify = %d\n", result2, verify2);
    
    return 0;
}

关键修正说明 #

• 新增选择记录数组：selected数组用于记录递归过程中每个位置是否选择抢劫，解决了原代码无法回溯标记房屋的问题。
• 记忆化递归逻辑：rob_rec函数在计算最大金额的同时，记录每一步的最优选择，确保每个位置仅计算一次，时间复杂度为O(n)。
• 回溯填充house数组：在rob函数中，根据selected数组的记录，从第0间房屋开始遍历，标记被抢劫的房屋（抢当前则跳过下一间，否则继续下一间）。
• 内存管理：动态分配memo和selected数组，使用后释放，避免内存泄漏。

测试结果 #

运行代码后，两个测试用例的返回金额与验证得分一致：

• 测试用例1：Result=4，Verify=4（抢劫房屋0和2）
• 测试用例2：Result=12，Verify=12（抢劫房屋0、2、4）

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