For solving which of the following problems dynamic programming can be used?

The correct answer is Option 1) Finding the longest common subsequence.

Key Points

• Dynamic Programming (DP) is a method used to solve problems by breaking them down into simpler sub-problems and storing the results to avoid redundant computation.
• The Longest Common Subsequence (LCS) problem involves finding the longest subsequence common to two sequences.
• It has overlapping subproblems and optimal substructure properties, making it ideal for dynamic programming.
• DP helps avoid recalculating solutions to subproblems by storing results in a 2D table (memoization or tabulation).

Additional Information

• Option 2 – Determining the height of a binary tree: Can be solved using recursion, not necessarily needing DP since subproblems don’t overlap significantly.
• Option 3 – Calculating the factorial of a number: Can be done via iteration or recursion. While memoization is possible, it's not efficient or required for such a straightforward calculation.
• Option 4 – Finding average of all elements in an array: Simple arithmetic calculation; does not involve subproblems or recursion, so DP is not relevant.

Conclusion: Dynamic Programming is best suited for problems like Longest Common Subsequence where overlapping subproblems and optimal substructure exist.