区间dp可以枚举左右端点,也可以考虑先枚举区间长度,这样小区间就会在大区间之前被计算。
大区间通过分界点由小区间转移。
例题 282. 石子合并
此题直接枚举区间长度和左端点,右端点不超过n。
AcWing 1068. 环形石子合并
此题可以考虑枚举区间长度和左端点,由于是环形数组,右端点可以越界,通过取模可以找到正确位置。
注意在枚举右端点和枚举中间点时均需要判断是否越界,如果越界需要取模。
如果区间为0-9,对num处理越界可以num%10;如果区间为1-9,对num处理越界可以(num-1)%9+1;
区间为m-n 可以(num-m)%(n-m+1)+m;
区间长度是多少就对多少取模,且区间右端点恰好不被取模影响,最后加上偏移。