先后选牌问题
初级递归
假设现在给你一个数组 长度为N （N > 0） 数组内部储存着int类型的值 大小为（1~100）
现在两个人先后选数字 有如下规定
- 只能选择最边界的数字
- 如果这个数字被选择了 则从数组中移除
那么我们其实可以写出先选和后选两个函数
一开始我们写出的递归函数如下
int f(vector<int>& arr , int L , int R)
int g(vector<int>& arr , int L , int R)
这里两个函数的意义分别是
- f优先选择的最大值
- g后手选择的最大值
参数的含义是
- arr 数组
- L 左边界
- R 右边界
代码表示如下
int f(vector<int>& arr , int L , int R) { if (L == R) { return arr[L]; } int p1 = arr[L] + g(arr , L + 1 , R ); int p2 = arr[R] + g(arr , L , R - 1); return max(p1 , p2); } int g(vector<int>& arr , int L , int R) { if (L == R) { return 0; } int p1 = f(arr , L + 1 , R); int p2 = f(arr , L , R -1); return min(p1 , p2); }
这里解释下为什么g函数中要取最小值
因为先手的人可能会拿走L或者R 给我们造成p1 或者 p2两种结果
因为先手的人要赢 所以说只可能会给我们最差的一种结果 所以一定会是较小的那个值
初级动态规划
这里变化的参数实际上就只有左边界和右边界
我们就可以围绕着这两个边界来建表
如果按照函数的依赖关系展开 我们很快就会发现重复项
所以说我们要围绕着重复项建表来达到动态规划的效果
而由于这里有两个函数 f 和 g 所以说 我们要建立两张表
我们以为L为横坐标 R为纵坐标建立两张表
L和R的范围是1 ~ R+1
代码表示如下
int _f2(vector<int>& arr , int L , int R , vector<vector<int>>& fmap , vector<vector<int>>& gmap) { if (fmap[L][R] != 0) { return fmap[L][R]; } int ans = 0; if ( L == R) { ans = arr[L]; } else { int p1 = arr[L] + _g2(arr , L+1 , R , fmap , gmap); int p2 = arr[R] + _g2(arr , L , R-1 , fmap , gmap); ans = max(p1 , p2); } fmap[L][R] = ans; return ans; }
int _g2(vector<int>& arr , int L , int R , vector<vector<int>>& fmap , vector<vector<int>>& gmap) { if (gmap[L][R] != 0) { return gmap[L][R]; } int ans = 0; if (L == R) { ans = 0; } else { int p1 = _f2(arr , L , R -1 , fmap , gmap); int p2 = _f2(arr , L + 1 , R , fmap , gmap); ans = min(p1 , p2); } gmap[L][R] = ans; return ans; }
动态规划
我们以L为横坐标 R为纵坐标画一个gmap图 并且将L == R的时候的值填入图中
我们可以发现该图的左下角我们是不需要的因为L不可能大于R
那么我们的gmap上右上角的随机一点是依赖于什么呢？
回归到我们最初的递归方程中
_f2(arr , L , R -1 , fmap , gmap); _f2(arr , L + 1 , R , fmap , gmap);
我们可以发现是依赖于fmap的 L R-1 以及 L+1 R
如果映射到fmap中 我们可以发现刚好是斜对角线上的两点 既然我们现在知道了斜对角线上的值 我们现在就可以开始填写这两张map表了
代码表示如下
int f3(vector<int>& arr , int L , int R) { vector<vector<int>> fmap( R + 1, vector<int>(R+1)); for (int i = 0 ; i < R + 1 ; i++) { for (int j = 0; j < R + 1 ; j++) { fmap[i][j] = 0; if (i == j) { fmap[i][j] = arr[i]; } } } vector<vector<int>> gmap( R+1 , vector<int>(R+1)); for (int i = 0 ; i < R + 1 ; i++) { for (int j = 0; j < R + 1 ; j++) { gmap[i][j] = 0; } } for (int startcol = 1 ; startcol < R + 1; startcol++ ) { int col = startcol; int row = 0; while (col < R + 1) { fmap[row][col] = max(gmap[row][col-1] + arr[row] , gmap[row+1][col] + arr[col]); gmap[row][col] = min(fmap[row][col-1] , fmap[row+1][col]); row++; col++; } } return fmap[L][R]; }
其实最关键的代码就是这两行
fmap[row][col] = max(gmap[row][col-1] + arr[col] , gmap[row+1][col] + arr[row]); gmap[row][col] = min(fmap[row][col-1] , fmap[row+1][col]);
我们可以发现 这其实就是将原来代码中的函数
int p1 = arr[L] + _g2(arr , L+1 , R , fmap , gmap); int p2 = arr[R] + _g2(arr , L , R-1 , fmap , gmap); ans = max(p1 , p2);
变成了表中的数字相加
这就是动态规划的一般套路
