Problem Explanation
In this problem we have to find all unique groups of 4 numbers in an array which add up to a given number.
Approach
This problem is solved using Dynamic Programming. We initialize a 2D matrix, and assume the row to represent the string A and the column to represent B.
- We initialize the first row and column as serial numbers as at first row or column we don’t consider any character from the other string. So to construct the string we have to perform the operations for all the characters till that index.
- If A[i] == B[i] we save dp[i][j] as dp[i-1][j-1] as no operation is required.
- Else we take dp[i][j] as the minimum of dp[i-1][j-1]+1, dp[i][j-1]+1, dp[i-1][j]+1 as have to perform one operation.