[CSES][Dynamic Programming] Removing Digits

cses.fi/proble...

[@utkarshpatil3180]

Your channel is criminally underrated bro, keep uploading such content.

[@codekhongngu]

Thanks bro , I am from VietNam

[@neatlystructured]

you are welcome! my greetings to VietNam

[@janplonka7143]

thanks for the video. i wasn't able to figure out the DP approach but I was able to code a recursive function to make it work, turned out pretty fast too. Watching now to try and understand DP.

[@neatlystructured]

glad this was helpful! thank you!

[@nvquanghuy2008]

From VietNam with Love

[@auhongan23]

Maybe using the greedy technique. public static int greedy(int n){
int cnt = 0;
while (n>0){
int max = -1;
int k = n;
while (k>0){
max = Math.max(max,k%10);
k/=10;
}
n-=max;
cnt++;
}
return cnt;
}

[@piyushsinha3756]

Nice Explanation DP approach is much simpler to code, however, with Queue the code will be much faster.
int n;
cin>>n;
vector dp(n+1, inf);
dp[n] = 0;
queue q;
q.push(n);
while(!q.empty()){
int cur = q.front();
q.pop();
int temp = cur;
while(temp!=0){
int val = temp%10;
if(dp[cur-val] > 1+dp[cur]){
q.push(cur-val);
dp[cur-val] = 1+dp[cur];
if(cur-val == 0){
break;
}
}
temp/=10;
}
}
cout

[@tusharmishra6702]

I did this with simple brute force. Just subtract the max digit in the number from the number itself

[@neatlystructured]

Great! But can you actually prove that it will always result in the right answer?

[@AntrikshParmar]

@@neatlystructured
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(deduct(sc.nextInt(), 0));
}
private static int deduct(int n, int depth) {
if (n == 0) return 0;
int temp = n;
int maxDigit = 0;
while (temp != 0) {
int mod = temp % 10;
maxDigit = Math.max(maxDigit, mod);
temp = temp / 10;
}
return 1 + deduct(n - maxDigit, depth + 1);
}
The above code works for all the input without TLE.

[@neatlystructured]

@@AntrikshParmar Great, i did not doubt that it wouldn't work, but the fact that it works is not proof that this greedy approach is sound. I wonder if one can prove that removing the maximal digit is always optimal.

[@madhavgupta2002]

#include
using namespace std;
map st;
int helper(int n, int steps=0)
{
if(n==0)
return steps;
if(n>n;
cout

[@piyushrajput0_]

I have used this code can anyone tell me what this is not a better approach rather than using dp
int maxdigit(int n)
{
int mx=INT_MIN;
while(n)
{
mx=max(mx,n%10);
n/=10;
}
return mx;
}
int main()
{

#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif

ll n;
cin>>n;
int cn=0;
while(n)
{
int mx=maxdigit(n);
n-=mx;
cn+=1;
}
cout

[@amanthakur4145]

I thik greedy works for this case

[@neatlystructured]

you are right! but if you cannot prove it and you have a dp solution at hand you should go with the dp solution!