dynamictestsol

Dynamic Programming Test Question 1: Fibonacci Sequence Write a dynamic programming algorithm to compute the n th Fibonacci number. Discuss the time and space complexity of your solution. Answer: A bottom-up approach can be used, starting with the first two Fibonacci numbers and building up to the n th number. This approach has O ( n ) time complexity and O (1) space complexity, as only the last two computed values need to be stored. Question 2: Longest Common Subsequence Describe an algorithm to find the longest common subsequence (LCS) of two strings. What is the time complexity of your algorithm? Answer: Use a 2D table to store the lengths of LCS at different points. The time complexity is O ( mn ), where m and n are the lengths of the two strings. The algorithm iterates over all pairs of indices in the two strings. Question 3: 0/1 Knapsack Problem Explain the dynamic programming solution to the 0/1 Knapsack problem. What are the time and space complexities? Answer: Create a 2D array dp where dp [ i ][ w ] represents the maximum value that can be obtained with a weight limit w using the first i items. Fill the array iteratively. The time and space complexities are both O ( nW ), where n is the number of items and W is the maximum weight capacity. Question 4: Coin Change Problem Describe an algorithm to find the minimum number of coins needed to make up a given amount. Assume you have an infinite supply of each coin denomination. Answer: Use a bottom-up approach to build a table dp where dp [ i ] is the minimum number of coins needed for amount i . Iterate over all coin denomina- tions for each amount. The time complexity is O ( mV ), where m is the number of denominations and V is the amount. 1