Which of the following problems can be solved by Dynamic Programming (DP) ?

Dynamic Programming (DP) is an algorithmic technique used to solve optimization problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations. The key characteristics required for a problem to be solvable by DP are overlapping subproblems and optimal substructure. Optimal Binary Search Tree (OBST) involves finding the most efficient BST for a given set of keys and frequencies, which exhibits both overlapping subproblems (calculating costs for subtrees) and optimal substructure. Similarly, the Longest Common Subsequence (LCS) problem finds the longest sequence common to two strings by comparing prefixes, where solutions to larger problems depend on smaller subproblems. The Knapsack Problem determines the maximum value of items that fit into a limited capacity, relying on decisions made at each step based on previous optimal solutions. Since all three problems possess the necessary properties of overlapping subproblems and optimal substructure, they are classic examples solvable using Dynamic Programming. Therefore, the correct answer is 'All of the above'.