牛客网-102-神奇数-京东

动态规划判断是否神奇（抄讨论区C++大佬的）

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static boolean judge(int a){
        int[] ints = new int[9];
        int sum = 0;
        for(int i = 0; i < 9; i++){
            ints[i] = a % 10;
            sum += ints[i];
            a = a / 10;
            if(a == 0){
                ints = Arrays.copyOfRange(ints, 0, i + 1);
                break;
            }

        }
        if(sum % 2 == 1){
            return false;
        }else{
            int target = sum / 2;

            boolean[] dp = new boolean[target + 1];//前i个数能够和为j
            dp[0] = true;
            for(int i = 0; i < ints.length; i++){
                for(int j = target; j >= ints[i]; j--){
                    dp[j] = dp[j] || dp[j - ints[i]];
                }
            }
            return dp[target];
        }
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int l = scanner.nextInt(), r = scanner.nextInt();
        int cnt = 0;
        for(int i = l; i <= r; i++){
            if(judge(i)){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}