nowcoder-神奇数

题目来源：

https://www.nowcoder.com/practice/56d818ae68134c12b26e81f41ecafb9e?tpId=90&tqId=30841&tPage=4&rp=4&ru=%2Fta%2F2018test&qru=%2Fta%2F2018test%2Fquestion-ranking

题目描述：

/**

• 东东在一本古籍上看到有一种神奇数,如果能够将一个数的数字分成两组,
• 其中一组数字的和等于另一组数字的和,我们就将这个数称为神奇数。
• 例如242就是一个神奇数,我们能够将这个数的数字分成两组,
• 分别是{2,2}以及{4},而且这两组数的和都是4.东东现在需要统计给定区间中有多少个神奇数,
• 即给定区间[l, r],统计这个区间中有多少个神奇数,请你来帮助他。
  */

思路：

设数字X，先求出X的每位数字存在List中，再求出X每位数字和，若为奇数则舍弃，若为偶数则判断是否是神奇数，通过动态规划，dp[i] [j]表示链表前i个数字能否求和得到j，则有dp[i] [j]=dp[i-1] [j] || dp[i-1] [j-list.get(i)];通过逆序循环将dp数组简化为一维数组。

参考代码：

public class Now_65 {
    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = bf.readLine().split(" ");
        int left = Integer.parseInt(strings[0]);
        int right = Integer.parseInt(strings[1]);
        int res = 0;
        for(int num = left ; num<=right ; num++){
            if(isMagic(num)){
                res++;
            }
        }
        System.out.println(res);
    }

    private static boolean isMagic(int num) {
        List<Integer> list = new LinkedList<>();
        int sum = 0;
        while (num>0){
            list.add(num%10);
            sum+=num%10;
            num/=10;
        }
        if(sum%2 != 0) return false;
        int mid = sum/2;
        int len = list.size();
        boolean[] dp = new boolean[mid+1];
        dp[0]=true;
        for(int i=0;i<len;i++){
            for(int j=mid;j>=list.get(i);j--){
                dp[j]=dp[j-list.get(i)] || dp[j];
            }
        }
        return dp[mid];
    }
}