-1
class Solution {
public:
    int n, memo[101];
    int minCost(vector<vector<int>>& costs) {
        n = costs.size();
        memset(memo, -1, sizeof(memo));
        return dfs(costs, 0, true, true, true);
    }
    
    int dfs(vector<vector<int>>& costs, int idx, bool red, bool green, bool yellow) {
        if (idx == n) {
            return 0;
        }
        if (memo[idx] != -1) {
            return memo[idx];
        }
        int a = 1e9, b = 1e9, c = 1e9;
        if (red == true)
            a = dfs(costs, idx + 1, false, true, true) + costs[idx][0];
        if (green == true)
            b = dfs(costs, idx + 1, true, false, true) + costs[idx][1];
        if (yellow == true)
            c = dfs(costs, idx + 1, true, true, false) + costs[idx][2];
        
        return memo[idx] = min({a, b, c});
    }
};

Problem : enter image description here

I created a recursive solution to the problem above, but since the solution is extremally inefficient O(3^N), I wanted to add memoization to my recursive function so it doesn't call overlapping sub problems. I believe I implemented it incorrectly since it gives the wrong output after applying memoization. What did I do wrong?

nsyh
  • 23
  • 3
  • 3
    *What did I do wrong?* -- What you did wrong is [not use a debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). Create a `main` program, pass the data you are saying doesn't work to the function, and single-step through the function to see where it diverges from your expectations. – PaulMcKenzie Nov 13 '22 at 22:23
  • 1
    *Why does Memoization not work here, and how can I make it work?* -- To add to the first comment, the "Why" part of the question is what you should be able to answer, as you wrote the code with a plan in mind. The "How to make it work" part of the question may, once you start to debug the problem, be answerable by yourself. Also on a side note: `memset(memo, -1, sizeof(memo));` -- Change that to `std::fill_n(memo, std::size(memo), -1);` – PaulMcKenzie Nov 13 '22 at 22:27
  • Thank you, I will try to debug it and see what I can find out. – nsyh Nov 13 '22 at 22:35
  • Yes, every program you write that has an issue, the "why?" should always be answerable by yourself after debugging the code. What may be easy or difficult is the "how do I fix?" , and that type of question is ok, but only after identifying *what* the problem is. It could be a misuse of C++, or you didn't code the algorithm correctly, or you find out that the code would never work and you start over with a new plan. – PaulMcKenzie Nov 13 '22 at 22:41
  • The "deug" it is pithy, but it is true. Humans always write bugs in their code. The "why is there a bug" answer is *you wrote code without removing the bugs*. This is why debugging is something you should do first, producing a [mcve], and then come here with your mcve. – Yakk - Adam Nevraumont Nov 14 '22 at 03:13

1 Answers1

1

The problem is that you memorize only by how deep you are (idx is always that for you) try using the whole state for memorizing. Eg swich all memo[idx] to memo[8*idx+4*red+2*green+blue]

Also resize memo 8 times to the max possible value of n+8 (If n<=100 it should be 808)

Assuming that your only problem is with the memorization now this should fix it

Botond Horváth
  • 929
  • 2
  • 15
  • Thank you, it fixed it. This makes a lot of sense! Is there another way I can fix this? Such as adding another dimension to my memo array? Or is the problem that my original recursive function is trash. – nsyh Nov 13 '22 at 22:45
  • You can do a few things 1.: make an `n*3` memo array and set the `memo[n][k]` for the `k`-th color 2.: Just do it with a loop, no recursion `for (i=0; i – Botond Horváth Nov 13 '22 at 22:58