-______-'s blog

By -______-, history, 9 months ago, In English,

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++)

Problem Link : http://codeforces.com/problemset/problem/489/B

Editorial Link : http://codeforces.com/blog/entry/14741

My Solution ( Greedy ) : 39216236


9 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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