1. [10 Points] State whether TRUE or FALSE:

1. The Dynamic Programming method yields the optimal solution in polynomial time.
2. The Optimal Binary Search Tree (OBST) is always a balanced tree.
3. The average number of comparisons for a key on a successful search may not always be the smallest possible in an OBST.