tgbaodeeptry's blog

By tgbaodeeptry, history, 4 years ago, In English

Recently, I have been learning Dynamic Programming and I implemeted it:

int n, m, k;

bool can(int x, int y, int rem) {
    if (x > n || y > m || rem < 0)
        return false;

    if (x == n && y == m && rem == 0)
        return true;

    return can(x + 1, y, rem - y) || can(x, y + 1, rem - x); 
}

I want to save a 'state' contains: (x, y, rem) I tried to use map with tuple like: map<tuple<int, int, int>, bool> but syntax is not correct.

Thanks guy

  • Vote: I like it
  • +7
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Sure map<tuple<int, int, int>, bool> works

But it will be much faster to use just plain arrays. Map can be better if keys are too big and you know that there not that much states.