SRM 555 DIV2 555

挺有意思的一道DP，題目大意是說，給你一個01構成的字元串，問你最少切幾刀，能把切成的子串都分成5的某一次方，如果不存在，就輸出-1。

DP的思路：1、從左往右掃，如果掃到的這一位與之前所有數構成的子串是5的某次方，就記錄f[i] = 1;

                      2、否則，再一重循環，找1~i中子串的數目。

僞代碼：

for i from 0 to s.size() - 1
{
   f[i] = -1;
   if(check(s.substr(0, i)))
       f[i] = 1;
   else
   {
       for(j from 1 to i)
           if(f[i-1] != -1 and check(s.substr(j, i - j + 1)))
           {
                if(f[i] == -1 or f[i] > f[j - 1] +1)
                    f[i] = f[j - 1] + 1;
            }
   }
}