Advertisement
Josif_tepe

Untitled

Dec 14th, 2021
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.57 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. int dp[1000000];
  5. int rek(int x)
  6. {
  7.     if(x==0)
  8.     {
  9.         return 0;
  10.     }
  11.     if(dp[x]!=-1)
  12.     {
  13.         return dp[x];
  14.     }
  15.     int y=x;
  16.     int cekor=2e9;
  17.     while(y>0)
  18.     {
  19.         int cifra=y%10;
  20.         int maks=-2e9;
  21.         if(cifra!=0)
  22.         {
  23.            cekor=min(cekor,rek(x-cifra)+1);
  24.         }
  25.         y/=10;
  26.  
  27.     }
  28.     dp[x]=cekor;
  29.     return cekor;
  30. }
  31. int main()
  32. {
  33.     int n;
  34.     cin>>n;
  35.     for(int i=0;i<=n;i++)
  36.     {
  37.         dp[i]=-1;
  38.     }
  39.     cout<<rek(n);
  40.     return 0;
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement