动态编程与记忆 rob house 问题

问：

这是我正在解决的问题： “你是一个职业强盗，计划抢劫街道上的房屋。房屋已编号 0,1,2，...，而你我假设房屋的数量最多是10000。每个房子都藏有一定数量的钱。阻止你抢劫他们每个人的唯一限制是相邻的房子有安全系统，如果两个相邻的房子在同一天晚上被闯入，他们会自动联系警察。

给定一个表示每所房子的金额的非负整数列表，确定 你今晚可以在不报警的情况下抢劫最多的钱。

我必须通过修改 、 来使用带有记忆的动态编程来使其工作，并引入一个可以由 调用的新函数。我无法更改.函数和另一个函数使用动态编程和记忆解决了问题，如下所示。它们应该具有时间复杂度 O（numHouses）。rob( )rob_rec()rob( )main( )rob( )rob_rec( )

我想实现这样的输出：

Score = 4
Check to verify solution:
 Score = 4
 Money = 1 2 3 1
 House = 1 0 1 0
Score = 12
Check to verify solution:
 Score = 12
 Money = 2 7 9 3 1
 House = 1 0 1 0 1
Score = 19
Check to verify solution:
 Score = 19
 Money = 10 7 3 9 1
 House = 1 0 0 1 0
Score = 605
Check to verify solution:
 Score = 605
 Money = 72 7 54 23 29 56 32 21 20 64 68 86 70 95 62 59 94 9 63 15
 House = 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0

以下是我当前的代码：

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

#define HOUSE_SIZE 20

int rob(int* money, int* house, int numHouses);

/*  Utility functions */
void clear_houses(int * house, int length); /* Clears array house[] */
void check_houses(int * house, int * money, int length);  /* Checks if houses are valid */
void random_fill(int * money, int length); /* Randomly fill array */
void display_array(int* a, int length);

int main()
{
    int money1[4] = {1, 2, 3, 1};
    int money2[5] = {2, 7, 9, 3, 1};
    int money3[5] = {10, 7, 3, 9, 1};
    int money4[HOUSE_SIZE];
    random_fill(money4, HOUSE_SIZE); /* Fill money4[ ] */

    int house[HOUSE_SIZE];

    clear_houses(house, 4);
    printf("Score = %d\n", rob(money1, house, 4));
    check_houses(house, money1, 4);

    clear_houses(house, 5);
    printf("Score = %d\n", rob(money2, house, 5));
    check_houses(house, money2, 5);

    clear_houses(house, 5);
    printf("Score = %d\n", rob(money3, house, 5));
    check_houses(house, money3, 5);

    clear_houses(house, HOUSE_SIZE);
    printf("Score = %d\n", rob(money4, house, HOUSE_SIZE));
    check_houses(house, money4, HOUSE_SIZE);
}

int rob(int* money, int* house, int numHouses)
{
    if (numHouses == 0) return 0;
    if (numHouses == 1) {
        house[0] = 1;
        return money[0];
    }

    int* maxMoney = (int*)malloc(numHouses * sizeof(int));
    maxMoney[0] = money[0];
    maxMoney[1] = (money[0] > money[1]) ? money[0] : money[1];

    for (int i = 2; i < numHouses; i++) {
        int robCurrentHouse = maxMoney[i - 2] + money[i];
        int skipCurrentHouse = maxMoney[i - 1];

        if (robCurrentHouse >= skipCurrentHouse) {
            house[i] = 1; // Mark the house as robbed
            maxMoney[i] = robCurrentHouse;
        } else {
            house[i] = 0; // Mark the house as skipped
            maxMoney[i] = skipCurrentHouse;
        }
    }

    int result = maxMoney[numHouses - 1];
    free(maxMoney);
    return result;
}

void display_array(int* a, int length)
{
    for (int k = 0; k < length; k++) {
        printf("%3d", a[k]);
    }
    printf("\n");
}

void random_fill(int * money, int length)
{
    int state = 11;
    for (int k = 0; k < length; k++) {
        state = (53 * state + 71) % 97;
        money[k] = state;
    }
}

void check_houses(int * house, int * money, int length)
{
    int check_score = 0;

    for (int k = 0; k < length; k++) {
        if (house[k] == 1) check_score += money[k];
    }

    printf("Check to verify solution:\n");
    printf("   Score = %d\n", check_score);
    printf("   Money = ");
    display_array(money, length);
    printf("   House = ");
    display_array(house, length);
    printf("\n");
}

void clear_houses(int * house, int length)
{
    for (int i = 0; i < length; i++) {
        house[i] = 0;
    }
}

我无法理解如何更新房屋数组，以便正确填充它并且该函数返回正确的值。谁能帮我？rob()

这是我的输出：

Score = 4
Check to verify solution:
   Score = 3
   Money =   1  2  3  1
   House =   0  0  1  0

Score = 12
Check to verify solution:
   Score = 10
   Money =   2  7  9  3  1
   House =   0  0  1  0  1

Score = 19
Check to verify solution:
   Score = 12
   Money =  10  7  3  9  1
   House =   0  0  1  1  0

Score = 605
Check to verify solution:
   Score = 741
   Money =  72  7 54 23 29 56 32 21 20 64 68 86 70 95 62 59 94  9 63 15
   House =   0  0  1  0  1  1  1  1  1  1  1  1  0  1  0  1  1  0  1  0