详细注释 | #数位染色#

#include <iostream>
#include <string>
using namespace std;
const int N = 200;
int dp[N];
int main() {
    long long n;
    cin >> n;
    //将整个数字变成 数字字符数组
    string s = to_string(n);
    // 计算整个数组的数字和
    int sum = 0;
    for(int i = 0; i < s.length(); i++){
        sum += (s[i]-'0');
    }
    if(sum%2) {  // 和为奇数时，一定No
        cout << "No" << endl;
        return 0;
    }
    // 和为偶数时，问题转变成 ： 给定一个容积为t的容器，每位数字表示物品的体积，装入物品，看是否能恰好装满容器
    int t = sum/2;   
    // 遍历每位 数字
    for(int i = 0; i < s.length(); i++){
        //遍历容量
        for(int j = t; j >= 0; j--){
            if(j-(s[i]-'0')>=0){
                // 当 容量大于物品i的体积时， dp[j] 不改变（不选物品i）， dp[j]改变（选物品i）
                dp[j] = max(dp[j], dp[j-(s[i]-'0')]+(s[i]-'0'));
            }
        }
    }
    if(dp[t] == t){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")