动态规划（制表法）范文及应用x

　动态规划（制表法）模板及应用 • int cache[100][100] 初始化为全体为 -1，这样在 cache 中存储的可以是其他任意非负整数，也可以是布尔类型 0/1 （true/false）， 1. 模板 int cache[2500][2500];

　// 初始化为 -1，memset(cache, -1, sizeof(cache));

　int someObscureFunction(int y, int x){

　if (...) return ...;

　int& ret = cache[y][x];

　// 返回的是引用类型，这样当后续对 ret 的修改也会直接反应在 cache 里。

　// 后面递归时调用自身得到的值都要赋给 ret

　if (ret != -1) return ret;

　...

　return ret;

　}

　 int main(int, char**){

　memset(cache, -1, sizeof(cache));

　return 0;

　}

　2. 应用举例 • 棋盘类游戏，起点在左上角，棋盘每一个位置上标注的是在该点能向右和向下走动的距离，问其能否到达最右下角。

　 int n;

　int board[100][100];

　int cache[100][100];

　 int jump_dp(int y, int x){

　if (y >= n || x >= n) return cache[y][x] = 0;

　if (y == n-1 && x == n-1) return cache[y][x] = 1;

　 int& ret = cache[y][x];

　if (ret != -1) return ret;

　int jmpSz = board[y][x];

　return cache[y][x] = jump_dp(y+jmpSz, x) || jump_dp(y, x+jmp_sz);

　}