模板 数位DP详解

int dfs(int len,int sum,bool limit)
{
    if(到达末尾) return sum==k;
    //状态枚举过直接返回 
    if(dp[len][sum][limit]!=-1) return dp[len][sum][limit];

    //判断当前位的上界 
    up=limit ? num[len]:1;

    int res=0;
    for(0~up) 
        res+=dfs(len+1,sum+(i==1),limit&&i==up)

    dp[len][sum][limit]=res;
    return res;
}