累加序列

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param arr string字符串
# @return bool布尔型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/ff244079fdaf4d8f9767887ec9582043?tpId=196&tqId=40512&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：fred-coder
    算法：
        本题类似于变种的斐波那契数列，f(n) = f(n - 1) + f(n - 2)，难点在于截取字符串使得当前选取数列，仍然满足斐波那契性质。
        设dfs(s, nums)，s表示当前剩余字符串，nums表示当前截取的满足条件的序列
            若s为空，nums的长度大于2，且最后一个数仍满足上述性质：
                返回True
            枚举可截取长度：1 ~ len(s)
                截取字符串strNum
                剪枝：
                    若s以"0"开头，截取长度大于1的话，截取的strNum均是无效的，退出循环
                strNum转数字num
                若当前nums长度小于2或者满足nums[-2] + nums[-1] == num，继续递归dfs(s[i:], nums + [num])

    复杂度：
        时间复杂度：O(n!)
        空间复杂度：O(n)
    """

    def AdditiveArray(self, arr):
        # write code here
        def dfs(s, nums):
            if not s and len(nums) > 2 and nums[-3] + nums[-2] == nums[-1]:
                return True

            for i in range(len(s)):
                strNum = s[:i + 1]
                if len(strNum) > 1 and strNum[0] == "0": # 如"01"，属于无效数字；若s[0] = "0"，则长度超过1的截取，都包含前缀"0"，都是无效数字
                    break
                num = int(strNum)
                if len(nums) < 2&nbs***bsp;nums[-2] + nums[-1] == num:
                    if dfs(s[i + 1:], nums + [num]):
                        return True
            return False

        return dfs(arr, [])


if __name__ == "__main__":
    sol = Solution()

    # arr = "12358"

    # arr = "19101929"

    arr = "191011"

    res = sol.AdditiveArray(arr)

    print res