Which of the following statements about Dynamic Programming is true?
Which data structure is commonly used in Dynamic Programming to store intermediate results?
1 Crore+ students have signed up on EduRev. Have you? Download the App |
What is the time complexity of the brute force approach for finding the Longest Increasing Subsequence (LIS) of a sequence of length n?
The Range Minimum Query (RMQ) problem is concerned with finding the ____________ element in a given range.
Which of the following tasks can be efficiently solved using Dynamic Programming?
Consider the following code:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(5))
What is the output of the code?
Consider the following code:
def knapsack(W, wt, val, n):
if n == 0 or W == 0:
return 0
if wt[n-1] > W:
return knapsack(W, wt, val, n-1)
else:
return max(val[n-1] + knapsack(W-wt[n-1], wt, val, n-1), knapsack(W, wt, val, n-1))
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(capacity, weights, values, len(weights)))
What is the output of the code?
Consider the following code:
def min_coin_change(coins, amount):
if amount == 0:
return 0
res = float('inf')
for coin in coins:
if amount - coin >= 0:
sub_res = min_coin_change(coins, amount - coin)
if sub_res != float('inf') and sub_res + 1 < res:
res = sub_res + 1
return res
coins = [1, 2, 5]
target_amount = 11
print(min_coin_change(coins, target_amount))
What is the output of the code?
Consider the following code:
def max_subarray_sum(arr):
max_sum = float('-inf')
current_sum = 0
for num in arr:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(array))
What is the output of the code?
Consider the following code:
def longest_increasing_subsequence(nums):
n = len(nums)
lis = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j] and lis[i] < lis[j] + 1:
lis[i] = lis[j] + 1
return max(lis)
sequence = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print(longest_increasing_subsequence(sequence))
What is the output of the code?
Consider the following code:
def count_paths(n, m):
if n == 1 or m == 1:
return 1
return count_paths(n-1, m) + count_paths(n, m-1)
print(count_paths(3, 4))
What is the output of the code?
Consider the following code:
def binomial_coefficient(n, k):
if k == 0 or k == n:
return 1
return binomial_coefficient(n-1, k-1) + binomial_coefficient(n-1, k)
print(binomial_coefficient(5, 2))
What is the output of the code?
Consider the following code:
def matrix_chain_multiplication(dims, i, j):
if i == j:
return 0
min_ops = float('inf')
for k in range(i, j):
ops = matrix_chain_multiplication(dims, i, k) + matrix_chain_multiplication(dims, k+1, j) + dims[i-1] * dims[k] * dims[j]
min_ops = min(min_ops, ops)
return min_ops
dimensions = [5, 10, 3, 12, 5, 50, 6]
n = len(dimensions)
print(matrix_chain_multiplication(dimensions, 1, n-1))
What is the output of the code?
Consider the following code:
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount]
coins = [1, 2, 5]
target_amount = 11
print(coin_change(coins, target_amount))
What is the output of the code?
Consider the following code:
def knapsack_dp(W, wt, val, n):
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
dp[i][w] = 0
elif wt[i-1] <= w:
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]
return dp[n][W]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack_dp(capacity, weights, values, len(weights)))
What is the output of the code?