数位dp算法leetcode.788

  public int rotatedDigits(int n) {
        Set<Integer> s1=new HashSet<>();//能翻转
        s1.add(1);
        s1.add(2);
        s1.add(0);
        s1.add(5);
        s1.add(6);
        s1.add(8);
        s1.add(9);
         Set<Integer> s2=new HashSet<>();//能翻转且不同
        s2.add(5);
        s2.add(2);
        s2.add(9);
        s2.add(6);
        int[] dp=new int[n+1];//1表示翻转且不同，0表示翻转相同，-1表示无法翻转
        int ans=0;
        //数位dp
        for(int i=1;i<n+1;i++){
            if(dp[i/10]==1){
                if(s1.contains(i%10)){
                    dp[i]=1;
                    ans++;
                }else dp[i]=-1;
            }else if(dp[i/10]==0){
                if(!s1.contains(i%10)){
                    dp[i]=-1;
                }else if(s2.contains(i%10)){
                    dp[i]=1;
                    ans++;
                }else dp[i]=0;
            }else dp[i]=-1;
        }
        return ans;
    }