动态规划(制表法)范文及应用.doc

第页共NUMPAGES2页
动态规划（制表法）范文及应用

动态规划（制表法）模板及应用bull;intcache[100][100]初始化为全体为-1，这样在cache中存储的可以是其他任意非负整数，也可以是布尔类型0/1（true/false），1.模板intcache[2500][2500];
//初始化为-1，memset(cache,-1,sizeof(cache));
intsomeObscureFunction(inty,int_){
if(...)return...;
intret=cache[y][_];
//返回的是引用类型，这样当后续对ret的修改也会直接反应在cache里。
//后面递归时调用自身得到的值都要赋给ret
if(ret!=-1)returnret;
...returnret;
}
intmain(int,char__){
memset(cache,-1,sizeof(cache));
return0;
}
2.应用举例bull;棋盘类游戏，起点在左上角，棋盘每一个位置上标注的是在该点能向右和向下走动的距离，问其能否到达最右下角。
intn;
intboard[100][100];
intcache[100][100];
intjump_dp(inty,int_){
if(y>=n||_>=n)returncache[y][_]=0;
if(y==n-1_==n-1)returncache[y][_]=1;
intret=cache[y][_];
if(ret!=-1)returnret;
intjmpSz=board[y][_];
returncache[y][_]=jump_dp(y+jmpSz,_)||jump_dp(y,_+jmp_sz);
}