Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### -______-'s blog

By -______-, history, 6 months ago, ,

I've successfully solved this problem using Greedy Approach but in the editorial it was given that the probelm can also be solved using Dynamic Programming.

Can someone help me with the DP solution ? (preferably in C++)

 » 6 months ago, # | ← Rev. 4 →   0 First, sort arrays a and b.Let dp[i][j] be the answer if we have only a[0..i] and b[0..j].dp[i][j] is maximum of: 0 1 if |a[i]-b[j]|<=1 dp[i-1][j-1]+1 if i-1>=0, j-1>=0 and |a[i]-b[j]|<=1 dp[i-1][j] if i-1>=0 dp[i][j-1] if j-1>=0 Answer will be dp[n-1][m-1].My Solution: 39227258