3-D DP против 2-D DP, кажется, не могу понять, почему мой код нельзя запомнить. ⇐ C++

[Anonymous]

Код: Выделить всё

class Solution {
public:
int countNeighborhoods(const vector& houses) {
int neighborhoods = 0;
int m = houses.size();
for (int i = 0; i < m; i++) {
if (houses[i] != 0 && (i == 0 || houses[i] != houses[i - 1])) {
neighborhoods++;
}
}
return neighborhoods;
}

int solve(vector& houses, vector& cost, int m, int n, int target, int idx, int tCost) {
if (idx >= m && target != 0)
return 1000000;
if (idx >= m && target == 0)
return tCost;

int ans = 1000000;

if (houses[idx] != 0) {
ans = min(ans, solve(houses, cost, m, n, target, idx + 1, tCost));
} else {
for (int i = 0; i < n; i++) {
bool left_same = (idx > 0 && houses[idx - 1] == i + 1);
bool right_same = (idx < m - 1 && houses[idx + 1] == i + 1);

houses[idx] = i + 1;

if (!left_same && !right_same) {
ans = min(ans, solve(houses, cost, m, n, target - 1, idx + 1, tCost + cost[idx][i]));
} else {
ans = min(ans, solve(houses, cost, m, n, target, idx + 1, tCost + cost[idx][i]));
}

houses[idx] = 0;
}
}

return ans;
}

int minCost(vector& houses, vector& cost, int m, int n, int target) {
int initialNeighborhoods = countNeighborhoods(houses);
int requiredNeighborhoods = target - initialNeighborhoods;
if (requiredNeighborhoods < 0) return -1;

int ans = solve(houses, cost, m, n, requiredNeighborhoods, 0, 0);
return (ans == 1000000) ? -1 : ans;
}
};

Выше приведен мой код, который я создал для следующего вопроса о лит-коде —
https://leetcode.com/problems/paint-house -iii/
Логика моего кода заключается в том, чтобы просто рекурсивно перебирать массив, раскрашивая дома всеми возможными цветами и используя операторы if, которые есть в коде, чтобы иметь возможность сказать, как я нужно изменить количество окрестностей, а затем рекурсивно вызвать функцию.
Кажется, код дает правильный ответ, хотя я не могу его запомнить, следующее решение решает проблему, используя вместо этого другую логику проверки количества окрестностей -

Код: Выделить всё

class Solution {
public:
int solve(vector& houses, vector& cost, int m, int n, int target, int idx, int neighborhoods, int last_color) {
if (idx == m) {
return (neighborhoods == target) ? 0 : 1e6; // Cost 0 if exact neighborhoods; else, a large invalid cost.
}
if (neighborhoods > target) return 1e6; // Invalid if neighborhoods exceed target

int ans = 1e6;
if (houses[idx] != 0) {
int new_neighborhoods = neighborhoods + (houses[idx] != last_color);
ans = solve(houses, cost, m, n, target, idx + 1, new_neighborhoods, houses[idx]);
} else {
for (int color = 1; color 

Подробнее здесь: [url]https://stackoverflow.com/questions/79128670/3-d-dp-vs-2-d-dp-cant-seem-to-figure-out-why-my-code-cant-be-memoized[/url]