数位DP

    int dp(int u,int mask,bool isLimit,bool isNum)
    //u表示当前要填的数位
    //mask利用二进制存储已经填入的数字。此项可选
    //isLimit表示当前数位是否收到限制，即前面数位都是与目标一一对应。若受到限制，最大可填s[i]-'0'；否则，最大可填9
    //isNum表示当前数位前是否填过数字（是否跳过）。若前未填，本轮可从1开填或跳过；否则本轮从0开填
    {
        if(u==len)
            return isNum;
        int res=0;
        if(!isNum)
            res=dp(u+1,mask,false,false);
        int up=isLimit ? s[u]-'0' : 9;
        int down=isNum ? 0:1;
        for(int i=down;i<=up;i++)
        {
            if(!(mask>>i&1))
                res+=dp(u+1,mask|(1<<i),isLimit&&i==up,true);
        }
        return res;
    }

记忆化搜索

class Solution {
public:
    int len;
    string s;
    int f[10][1<<10];//memset(f,-1,sizeof f);
    int dp(int u,int mask,bool isLimit,bool isNum)
    {
        if(u==len)
            return isNum;
        if(!isLimit&&isNum&&f[u][mask]>=0)
        //当isLimit为true时，前面数位都已确定，并不是重复搜索，仅会搜索此种情况一次。
        //当isNum为false时，前面都为空，并不是重复搜索，仅会搜索此种情况一次。
            return f[u][mask];
        int res=0;
        if(!isNum)
            res=dp(u+1,mask,false,false);
        int up=isLimit ? s[u]-'0' : 9;
        int down=isNum ? 0:1;
        for(int i=down;i<=up;i++)
        {
            if(!(mask>>i&1))
                res+=dp(u+1,mask|(1<<i),isLimit&&i==up,true);
        }
        if(!isLimit&&isNum)
            f[u][mask]=res;
        return res;
    }
};

模板实例1
待续