Problem statement: http://www.spoj.com/problems/ADFRUITS/

The thing that you are looking for is called shortest common supersequence(or just SCS).

The length of SCS(a,b) and be computed using simple DP:

Let dp[i][j] is the length of the shortest common supersequence of a[1],...,a[i] and b[1],...,b[j].

Then there are two cases:

1) If a[i]=b[j], then dp[i][j]=1+dp[i-1][j-1].

2) If a[i]!=b[j], then dp[i][j]=1+min(dp[i-1][j],dp[i][j-1]).

Now, think how to restore the SCS after computing the dp array.