Link: https://leetcode.com/problems/partition-string-into-minimum-beautiful-substrings/description/
## 思路
基本型II dp
If ```s[i]```, ```s[i+1]```..```s[j]``` is pow of 5,
then ```dp[j+1] = min(dp[j+1], dp[i]+1)```
where ```dp[j]``` means the minimum partition for ```j``` first letters.
要注意他找的是pow of 5 而不是5的倍数
因此不能用```cur%5==0```检查
由于15625是15位binary string能表示的最大的power of 5
因此我们用```15625%cur==0```检查
## Code

class Solution:
    def minimumBeautifulSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [0]+[inf]*n
        for i in range(n):
            if s[i]=='1':
                cur = 0
                for j in range(i, n):
                    cur = cur*2+int(s[j])
                    if 15625 % cur == 0:
                        dp[j+1] = min(dp[j+1], dp[i]+1)
        return dp[n] if dp[n]<inf else -1