fork download
copy 
  1. #include <iostream>
  2. #include <climits>
  3. using namespace std;
  4.  
  5. int*dp;
  6. int rec(int n)
  7. {
  8.  
  9. 	if(n == 0)
  10. 	{
  11. 		return 0;
  12. 	}
  13.  
  14. 	if(dp[n] != -1)
  15. 	{
  16. 		return dp[n];
  17. 	}
  18.  
  19. 	//cout<<"n="<<n<<endl;
  20.  
  21. 	string S = to_string(n);
  22. 	int ans = INT_MAX;
  23. 	for(int i=0;i<S.length();i++)
  24. 	{
  25. 		if(S[i] != '0')
  26. 		{
  27. 			ans = min(ans,rec(n - (S[i]-'0'))+1);
  28. 		}
  29. 	}
  30.  
  31. 	dp[n] = ans;
  32. 	return ans;
  33. }
  34.  
  35.  
  36. int main() {
  37.  
  38. 	int n;
  39. 	cin>>n;
  40.  
  41. 	dp = new int[n+1];
  42. 	for(int i=0;i<=n;i++)
  43. 	{
  44. 		dp[i]=-1;
  45. 	}
  46. 	rec(n);
  47. 	cout<<dp[n]<<endl;
  48. 	return 0;
  49. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
27
stdout
copy 
5
https://ideone.com/6SMNFL
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!