数位染色

#include <iostream>
#include <vector>
using namespace std;

int main() {

long long x; cin>>x;
vector<int> nums;
int sum=0;
while(x){
    int t = x%10;
    nums.push_back(t);
    sum += t;
    x /= 10;
}
if((sum&1)==1) cout<<"No";
else{
    int capacity = sum>>1;
    vector<bool> dp(capacity+1, false);
    dp[0] = true;
    for(int v : nums){
        for(int j=capacity; j>=v; j--){
            if(dp[j-v]){
                dp[j] = dp[j-v];
            }
        }
    }
    cout<<(dp[capacity] ? "Yes" : "No");
}
}

def ans():
    nums = list(map(int , list(input())))
    sum_num = sum(nums)
    if sum_num % 2 == 1:
        print("No")
        return
    else:
        target = sum_num // 2
    dp = [0] * (target+1)
    dp[0] = 1
    for n in nums:
        j = target
        while j >= n:
            dp[j] += dp[j-n]
            j -= 1
    res = "Yes" if dp[target] else "No"
    print(res)
ans()

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long num = in.nextLong();
        String[] numStrs = Long.toString(num).split("");
        int[] nums = new int[numStrs.length];
        int sum = 0;
        for (int i = 0; i < numStrs.length; i++) {
            nums[i] = Integer.parseInt(numStrs[i]);
            sum += nums[i];
        }
        if (sum % 2 == 1) {
            System.out.println("No");
        } else {
            int target = sum / 2;
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int n : nums) {
                int j = target ;
                while (j >= n) {
                    dp[j] += dp[j - n];
                    j--;
                }
            }
            if (dp[target] != 0) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}