数位dp1

数位dp

package com.zhang.reflection.面试.算法模版.动态规划;
import java.util.Scanner;
/**
 * 数位dp：数位dp是一种计数用的dp，一般就是要统计一个区间[le,ri]内满足一些条件数的个数。
 * 所谓数位dp，字面意思就是在数位上进行dp咯。数位还算是比较好听的名字，数位的含义：一个数有个位、十位、百位、千位......数的每一位就是数位啦！
 *
 * 
 */
public class 数位dp {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        int sum=0;
        int[] nums=new int[s.length()];
        for(int i=0;i<s.length();i++){
            nums[i]=s.charAt(i)-'0';
            sum+=nums[i];
        }
        //如果为奇数，则不能
        if(sum%2==1){
            System.out.println("No");
            return ;
        }
        //如果为偶数，则转化为01背包问题
        sum=sum/2;
        boolean[] dp=new boolean[sum+1];
        dp[0]=true;
        for(int i=0;i<s.length();i++){
            for(int j=sum;j>=nums[i];j--){
                if(dp[j-nums[i]]==true){
                    dp[j]=true;
                }
            }
        }
        System.out.println(dp[sum]==false?"No":"Yes");
    }
}