题目
累加数 是一个字符串，组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给你一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
说明：累加序列里的数 不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例 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
解题
方法一：DFS
第一个数的起始位置一定是i=0，第二个数的起始位置j，第三个数的起始位置k
class Solution { public: bool isAdditiveNumber(string num) { int i=0; for(int j=i+1;j<num.size();j++){ for(int k=j+1;k<num.size();k++){ if(dfs(num,i,j,k)) return true; } } return false; } bool dfs(string& num,int i,int j,int k){ if((num[i]=='0'&&j-i>1)||(num[j]=='0'&&k-j>1)) return false;//如果首字母为’0‘，但长度不为1 string a=num.substr(i,j-i); string b=num.substr(j,k-j); string sum=add(a,b); int n=sum.size(); if(k+n-1>num.size()-1||sum!=num.substr(k,n)) return false;//累加结果sum长度大于最大长度，或者sum和下一个数不相等 if(k+n-1==num.size()-1) return true;//sum和下一个数相等，而且到了num末尾 return dfs(num,j,k,k+n);//继续遍历下一组累加数 } //字符串相加 string add(string& a,string& b){ string res; int add=0; int i=a.size()-1; int j=b.size()-1; while(i>=0||j>=0||add>0){ int x=i>=0?a[i--]-'0':0; int y=j>=0?b[j--]-'0':0; add+=x+y; res+=add%10+'0'; add/=10; } reverse(res.begin(),res.end()); return res; } };
