Share my C++ DP Solution


  • 0
    W

    I think this solution works for removing any number from 1 to 9,just change the "except " to that number.

        int newInteger(int n)
        {
            int except=9;
            
            vector<vector<int>> dp(32,vector<int>(10,0));
            for(int i=0;i<10;i++) 
            {
                if(i==except) continue;
                dp[1][i]=1;
            }
            
            int len=1;
            for(int i=2;i<32;i++)
            {
                long long count=0;
                for(int j=0;j<10;j++)
                {
                    if(j==except) continue;
                    for(int k=0;k<10;k++) 
                    {
                        dp[i][j]+=dp[i-1][k];
                    }
                    count+=dp[i][j];
                }
                len=i;
                if(count>=n) break;
            }
            
            int ret=0;
            for(int l=len;l>=1;l--)
            {
                int j=0;
                while(n>=dp[l][j])
                {
                    n-=dp[l][j];
                    j++;
                }
                ret=ret*10+j;
            }
            
            return ret;
        }
    

  • 0
    L

    Can you add comments to your code?


  • 0
    S

    little bit confused in the last part of your code, if you can add commits


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.