这道题的dp思路是自上推下么?
f[i, j] i表示栈里面的数量,j表示操作序列里的数量。
那么状态转移不应该是: f[i, j] = f[i - 1, j + 1] + f[i + 1, j]么?
当前的 i, j由上一步压入 [i - 1, j + 1] 和上一步弹出 [i + 1, j] 得到的么?
为什么正解是如下的思路? 我这个由前推后的思路哪里有问题呢?
for(int j = 0; j <= n; j++)
for(int i = 0; i <= n - j; i++)
{
if(!j) {f[i][j] = 1; continue;}
if(i > 0) f[i][j] = f[i - 1][j] + f[i + 1][j - 1];
else f[i][j] = f[i + 1][j - 1];
}