滑雪dp

经典的dp题：滑雪-dp记忆化深搜

DP 记忆化深搜
(1) 如果只有1个点，结果就是1
(2) 如果有两个点，从1->2， 结果就是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;
    }
};