To 3 --- 最后的编程挑战

算是比较典型的dfs

每以为两种情况 这个不难

边界条件比较不容易判断，做的时候，调试了不少次才可

sum是全部位上的和，只有sum%3==0就可

删除：sum剪掉这一位上的数字

不删除：记得i要移动，意义是判断第i位

至于用string存储，感觉这个还是很容易想出的。

dfs中我感觉写的并不是太好，大佬看见的话，可以评论发下代码哦~。

#include <iostream>
using namespace std;
using ll = long long;
string N;
ll dfs(int k, int sum, int i)
{
    
    ll res = 1e18;
    // 0：全部都删去的情况
    if (sum == 0)
        return res;
    if (sum % 3 == 0)
        return k;
    // 将第一个数字删除 i也是-1 所以sum%3的判断在上面
    if (i == -1)
        return res;
    // 删除与否第i的数的两种情况
    res = min(res, dfs(k, sum, i - 1));
    res = min(res, dfs(k + 1, sum - N[i] + '0', i - 1));
    return res;
}
int main()
{
    
    cin >> N;
    int sum = 0;
    for (auto e : N)
        sum += e - '0';
    ll res = dfs(0, sum, N.size() - 1);
    cout << (res == 1e18 ? -1 : res) << endl;
    return 0;
}