这道题怎么想到是区间dp的。
对于长度为1的区间,很容易想到是1,
对于长度等于2的区间,我们要考虑两个因素,1是刷子的长度,2是两个区间
如果超出了刷子的长度,很明显答案要加1,
如果明显答案可以继承,
再考虑长度为3的刷子的时候,也是一样 不妨假设断点设在2位子如果 这里k从左到右,左开右闭,等于f[i+1][k]+f[k+1][j],即可以从f[k+1][j]上继承过来 这里f[i+1][k]再i=k时为0
如果长度大于k的话,则拆分成两个区间取最小值
这道题怎么想到是区间dp的。
对于长度为1的区间,很容易想到是1,
对于长度等于2的区间,我们要考虑两个因素,1是刷子的长度,2是两个区间
如果超出了刷子的长度,很明显答案要加1,
如果a[i]==a[i+1]明显答案可以继承,
再考虑长度为3的刷子的时候,也是一样 不妨假设断点设在2位子f[i][k],f[k+1][j]如果a[i]==a[k+1] 这里k从左到右,左开右闭,等于f[i+1][k]+f[k+1][j],即可以从f[k+1][j]上继承过来 这里f[i+1][k]再i=k时为0
如果长度大于k的话,则拆分成两个区间取最小值