前言
累加数是一个字符串，组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给定一个只包含数字 ’0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是累加数。
说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
正文
问题来源
本问题来自leetcode上的306题。
问题描述
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1:
输入: "112358"
输出: true
解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
示例 2:
输入: "199100199"
输出: true
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
分析：
func stringAdd(num1, num2 string) string {
l1 := len(num1)
l2 := len(num2)
var lmax int
var lmin int
if l1 > l2 {
lmax = l1
lmin = l2
} else {
lmax = l2
lmin = l1
num1, num2 = num2, num1
}
buf := make([]byte, lmax + 1)
var carry uint8 = 0
i := 0
for ; i < lmin; i++ {
buf[lmax-i] = num1[lmax-i-1] - '0' + num2[lmin-i-1] + carry
if buf[lmax-i] > '9' {
buf[lmax-i] = buf[lmax-i] - 10
carry = 1
} else {
carry = 0
}
}
for ; i < lmax; i++ {
buf[lmax-i] = num1[lmax-i-1] + carry
if buf[lmax-i] > '9' {
buf[lmax-i] = buf[lmax-i] - 10
carry = 1
} else {
carry = 0
}
}
if carry == 1 {
buf[0] = '1'
}
if buf[0] == 0 {
return string(buf[1:])
}
return string(buf)
}
func dp(num, num1 string, i, j int) bool {
//fmt.Println(i)
if j == len(num) {
fmt.Println(j)
return true
}
if j - i > 1 && num[i] == '0' {
return false
}
//fmt.Println(string(num[i:j]),i,j)
ret := stringAdd(num1, string(num[i:j]))
if strings.HasPrefix(string(num[j:]), ret) {
//fmt.Println(string(num[j:]), num1, string(num[i:j]), ret, i, j)
if dp(num, string(num[i:j]), j, j+len(ret)) {
return true
}
}
return false
}
func isAdditiveNumber(num string) bool {
l := len(num)
for i := 1; i < (l+1)/2; i++ {
for j := i + 1; j - i < (l+1)/2; j++ {
if j - i > 1 && num[i] == '0' {
continue
}
if dp(num, string(num[:i]), i, j) {
return true
}
}
}
return false
}
总结：
勤思考。
结语
不管怎么样好好加油。
