經(jīng)典的dp題：滑雪-dp記憶化深搜

DP 記憶化深搜
(1) 如果只有1個點，結(jié)果就是1
(2) 如果有兩個點，從1->2， 結(jié)果就是2
用f(i,j) 表示以(i,j)為終點的最長路徑。
如果有多個點：
f(i, j) = max{從他周圍的四個高處 過來 } + 1; 其中上下左右4個高處f(x,y)是個子問題。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
/**
 * DP 記憶化深搜
 * 把當前位置g[i][j]作為終點, f(i, j) = max{1, 從他周圍的四個高處 過來 + 1}
 */
class Solution {
private:
    struct position{
        int x, y;
    };
    //右/下/左/上
    const position dir[] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
public:
    //把當前位置g[i][j]作為終點, f(i, j) = max{1, 從他周圍的四個高處 過來 + 1}
    int dp_search(vector<vector<int>>& graph, int i, int j, vector<vector<int>>& cache) {
        if (cache[i][j]) {
            return cache[i][j];
        }
        cache[i][j] = 1;
        for(int k = 0; k < 4; k++) {
            int x = i + dir[k].x;
            int y = j + dir[k].y;
            // valid coordinates
            if (x >= 0 && x < graph.size() && y >= 0 && y < graph[0].size()) {
                if (graph[x][y] > graph[i][j]) {
                    cache[i][j] = std::max(cache[i][j], dp_search(graph, x, y, cache) + 1);
                }
            }
        }
        return  cache[i][j];
    }

    int solution(vector<vector<int>> graph){
        if (graph.size() <= 0) {
            return 0;
        }
        int n = graph.size();
        int m = graph[0].size();
        vector<vector<int>> cache(n + 2, vector<int>(m + 2, 0));

        int max_path = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cache[i][j] = dp_search(graph, i, j, cache);
                max_path = std::max(max_path, cache[i][j]);
            }
        }
        return max_path;
    }
};