算法注意---5、动态规划填表的时候,对于能够填表的点才填表
一、总结
一句话总结:
动态规划填表的时候,对于能够填表的点才填表,不能填表的点比如初始状态就不能动(比如过河卒)
1、f(n)=f(n-1)+f(n-2)+...+f(n-k)在写成代码的注意点是什么?
这里的第一层循环i代表n,第二层循环j代表k,而递推表达式里面是f(n-k),所以对应的代码就是f[i-k]
//确定k+1到第n项 for(int i=k+1;i<=n;i++){ for(int j=1;j<=k;j++){ //注意这里一定是f[i-j] f[i]=(f[i]+f[i-j])%mod; } }
2、c++初始化二维数组?
分行进行初始化:int a[2][3]={{1,2,3},{4,5,6}};
3、递归一般是由终止条件到达初始条件,比如过河卒?
那么递归的关系式应该是f[i][j]=f[i-1][j]+f[i][j-1],而不是f[i][j]=f[i+1][j]+f[i][j+1]
4、限制性动态规划的易错点,比如过河卒的题目?
直接填表更新状态会有问题,那些被马控制的点不能被更新状态,始终要是0
|||-begin
//如果直接这样写,那么马控制点点也会被更新, //马控制的点始终是0,不能被更新 for(int i=1;i<=bx;i++){ for(int j=1;j<=by;j++){ f[i][j]=f[i-1][j]+f[i][j-1]; } }
|||-end
而如上写法被马控制的点会被更新 //如果直接这样写,那么马控制点点也会被更新, //马控制的点始终是0,不能被更新 for(int i=1;i<=bx;i++){ for(int j=1;j<=by;j++){ if(!control[i][j]) f[i][j]=f[i-1][j]+f[i][j-1]; } }
5、对于有负数情况的递推(动态规划)问题,比如过河卒,f[i][j]=f[i-1][j]+f[i][j-1]?
采用的策略一般都是加数让它变成正数
6、动态规划填表的时候,对于能够填表的点才填表,不能填表的点比如初始状态就不能动(比如过河卒)?
动态规划填表的时候,对于能够填表的点才填表,不能填表的点比如初始状态就不能动(比如过河卒)
//做动态规划 for(int i=0;i<=bx;i++){ for(int j=0;j<=by;j++){ //if(i||j) //动态规划填表的时候,对于能够填表的点才填表 //不能填表的点比如初始状态就不能动 if(f[i][j]==-1) { //f[i][j]=f[i-1][j]+f[i][j-1] if(i-1>=0&&j-1>=0) f[i][j]=f[i-1][j]+f[i][j-1]; else if(i-1>=0) f[i][j]=f[i-1][j]; else if(j-1>=0) f[i][j]=f[i][j-1]; else f[i][j]=0; } } }
二、内容在总结中
博客对应课程的视频位置: