不能写为左闭右闭区间的原因是假如 f[i-1][j] 根本就不存在,它的值是 0,按照左闭右开的写法这样就会导致左端点为 0 从而返回值是 0,这样是正确的,因为不存在根本就无法转移。
而按照左闭右闭的写法的话就会导致明明是 0却认为这是上个区间的右端点,导致下个区间的左端点变成1,从而返回错误答案。
错误代码:
f[a][i]=i;
......
if(!f[i][j])
f[i][j]=f[i-1][f[i-1][j]+1];
正确代码:
f[a][i]=i+1;
......
if(!f[i][j])
f[i][j]=f[i-1][f[i-1][j]];

错误输出:左图。
正确输出:右图。