题解 | #数位染色#

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.next();
            String res = process(str) ? "Yes" : "No";
            System.out.println(res);
        }
    }
    
    public static boolean process(String str) {
        if (str == null || str.length() < 1) {
            return false;
        }
        char[] arr = str.toCharArray();
        int sum = 0;
        int n = arr.length;
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            sum += (arr[i] - '0');
            nums[i] = arr[i] - '0';
        }
        int half = sum / 2;
        if (sum % 2 != 0) {
            return false;
        }
        boolean[] dp = new boolean[half + 1];
        dp[0] = true;
        dp[nums[0]] = true;
        for (int i = 1; i < n; i++) {
            for (int j = half; j >= nums[i]; j--) {
                dp[j] = dp[j] || dp[j - nums[i]];
            }
            if (dp[half]) {
                return true;
            }
        }
        return false;
    }
    
    
}