写在最前面:吹爆滚动数组!!!!!!!太好用了叭!!!快学它!!!
题目大意:求最少增加几个字符可以使字符串s变成回文串
要注意一下下标ij的循环顺序
由于计算f[i]是要计算f[i+1],所以i要从后往前枚举
由于计算f[j]是要计算f[j-1]所以j要从前往后枚举
那我们就来算一下空间复杂度叭
(和f数组相比,s数组过小可鉯忽略不计;
一个int,4个字节)
所以那我们该怎么办呢
还记得我写在最前面的话么??!!!
这个时候滚动数组上场了!!!
而i是顺序循环只做一遍循环完就不要了
也就是说只需要保留上一组数据即可
根据i的奇偶性进行存储
妥妥地没有超是不是超棒!!!