dp思路问题
查看原帖
dp思路问题
1331924
pangmingyu01楼主2024/9/5 09:59

这道题的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];
	}

2024/9/5 09:59
加载中...