问题描述
小Y有一个数字串，她希望通过分隔这个字符串来获得一些子串，每个子串代表一个数字。她的目标是最大化能获得的是 3 的倍数的数字的数量。分隔后的数字串不能包含前导零（但数字 0 本身是允许的），因为 0 也被视为 3 的倍数。
例如，对于数字串 1123，可以将其分割为 [1, 12, 3]，其中 12 和 3 是 3 的倍数，因此小Y最多可以获得 2 个是 3 的倍数的数字。
测试样例
样例1：
输入：
n = "1123"
输出：2
样例2：
输入：
n = "300"
输出：3
样例3：
输入：
n = "987654321"
输出：6
题解：
字符串中每一个数字都有两种情况，一个是选，一个是不选，所以使用回溯或者动态规划求解比较简单，这里选择回溯法。
回溯DFS中的i是当前数字，last是上一个数字是否选取，1为选，0为不选，sum是当前选择子串的和，用来判断是否是3的倍数，cnt是3的倍数的子串的个数。
剩下的就是编写退出条件，因为要找所有的子串，所以退出条件就是i>=n.size()，而判断是否为3的倍数，除了检测3的问题，还要考虑上一个数是否选取的问题。
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;
int maxcnt=0;
int found(int i,int last,int sum,string n,int cnt){
int t=0;
if((sum%3==0 && last==1) || i>=n.size()){
if(sum%3==0 && last==1){
cnt++;t=1;
}
if(i>=n.size()){
if(cnt>maxcnt){
maxcnt=cnt;
}
return 0;
}
}
found(i+1,1,sum+(n[i]-48),n,cnt);
found(i+1,0,0,n,cnt);
return 0;
}
int solution(string n) {
maxcnt=0;
// write code here
found(0,0,0,n,0);
return maxcnt;
}
int main() {
cout << (solution("1123") == 2) << endl;
cout << (solution("300") == 3) << endl;
cout << (solution("987654321") == 6) << endl;
}