# 14090 - Domo's Treasure Hunt
## Brief
You are tasked to find the maximum possible sum of a path from the top left corner of a 2D array to the bottom right corner.
For detailed explanation, visit [this link](https://acm.cs.nthu.edu.tw/problem/14090/).

## Idea
Before arriving at a position (x, y) that is not (0, 0), Domo must have been either to (x, y-1) or (x-1, y). Therefore, the maximum money that he can obtain once he arrives at (x, y) could be theoretically calculated by:

#include <stdio.h>

int MONEY_AT_[1024][1024];

unsigned long long MAXIMUM_MONEY_AT_(int x, int y) {
    unsigned long long maximumMoneyAtUpperCell = (y>0)? MAXIMUM_MONEY_AT_(x, y-1): 0;
    unsigned long long maximumMoneyAtLeftCell = (x>0)? MAXIMUM_MONEY_AT_(x-1, y): 0;
    return (maximumMoneyAtLeftCell > maximumMoneyAtUpperCell) ?
        MONEY_AT_[x][y] + maximumMoneyAtLeftCell :
        MONEY_AT_[x][y] + maximumMoneyAtUpperCell;
}

int main() {
    int M, N;
    scanf("%d%d", &M, &N);
    for(int n = 0; n < N; n++) {
        for(int m = 0; m < M; m++) {
            scanf("%d", &MONEY_AT_[m][n]);
        }
    }
    printf("%llu\n", MAXIMUM_MONEY_AT_(M-1, N-1));
}

But, despite the theoretical beauty, the code won't work in practice, at least not for a humongous input size like a 1024-by-1024 array. What's the problem? Well, try modifying the code:

unsigned long long MAXIMUM_MONEY_AT_(int x, int y) {
    printf("MAXIMUM_MONEY_AT_(%d, %d) called\n", x, y);
    unsigned long long maximumMoneyAtUpperCell = (y>0)? MAXIMUM_MONEY_AT_(x, y-1): 0;
    unsigned long long maximumMoneyAtLeftCell = (x>0)? MAXIMUM_MONEY_AT_(x-1, y): 0;
    return (maximumMoneyAtLeftCTell > maximumMoneyAtUpperCell) ?
        MONEY_AT_[x][y] + maximumMoneyAtLeftCell :
        MONEY_AT_[x][y] + maximumMoneyAtUpperCell;
}

If you input the sample input into the program, you'll see that the function is called 465 times, but many of the function calls are duplicates. Since the function makes no change to external variables. As long as `MONEY_AT_` doesn't change, the return value will be the same when given same arguments. In other words, calling the function with the same argument you called before is a waste of time. Instead, you can either <font color=red>store the value you finished calculating somewhere and access the value whenever the function is called</font> or <font color=blue> calculate the cheap-to-compute values first and use the computed value to eventually get to the larger values</font>. These two approaches are known as **memoization** and **tabulation** respectively, and they are the ways you can implement the Dynamic Programming.

## Solution

<details>
<summary>Memoization Solution</summary>

#include <stdio.h>

int MONEY_AT_[1024][1024];
unsigned long long MAXIMUM_MONEY_AT_[1024][1024];

unsigned long long GET_MAXIMUM_MONEY_AT_(int x, int y) {
    if(MAXIMUM_MONEY_AT_[x][y] != 0)
        return MAXIMUM_MONEY_AT_[x][y];
    unsigned long long maximumMoneyAtUpperCell = (y>0)? GET_MAXIMUM_MONEY_AT_(x, y-1): 0;
    unsigned long long maximumMoneyAtLeftCell = (x>0)? GET_MAXIMUM_MONEY_AT_(x-1, y): 0;
    MAXIMUM_MONEY_AT_[x][y] = (maximumMoneyAtLeftCell > maximumMoneyAtUpperCell) ?
        MONEY_AT_[x][y] + maximumMoneyAtLeftCell :
        MONEY_AT_[x][y] + maximumMoneyAtUpperCell;
    return MAXIMUM_MONEY_AT_[x][y];
}

int main() {
    int M, N;
    scanf("%d%d", &M, &N);
    for(int n = 0; n < N; n++) {
        for(int m = 0; m < M; m++) {
            scanf("%d", &MONEY_AT_[m][n]);
        }
    }
    printf("%llu\n", GET_MAXIMUM_MONEY_AT_(M-1, N-1));
}

</details>

<details>
<summary>Tabulation Solution</summary>

#include <stdio.h>

int MONEY_AT_[1024][1024];
unsigned long long MAXIMUM_MONEY_AT_[1024][1024];

int main() {
    int M, N;
    scanf("%d%d", &M, &N);
    for(int n = 0; n < N; n++) {
        for(int m = 0; m < M; m++) {
            scanf("%d", &MONEY_AT_[m][n]);
        }
    }
    for(int n = 0; n < N; n++) {
        for(int m = 0; m < M; m++) {
            unsigned long long maximumMoneyAtUpperCell = (n>0)? MAXIMUM_MONEY_AT_[m][n-1]: 0;
            unsigned long long maximumMoneyAtLeftCell = (m>0)? MAXIMUM_MONEY_AT_[m-1][n]: 0;
            MAXIMUM_MONEY_AT_[m][n] = (maximumMoneyAtLeftCell > maximumMoneyAtUpperCell) ?
                MONEY_AT_[m][n] + maximumMoneyAtLeftCell :
                MONEY_AT_[m][n] + maximumMoneyAtUpperCell;
        }
    }
    printf("%llu\n", MAXIMUM_MONEY_AT_[M-1][N-1]);
}

</details>