Dynamic Programming - 1 - Free MCQ Practice Test with solutions, Software

Which of the following best describes Dynamic Programming?

What is the main advantage of using Dynamic Programming?

What is memoization in Dynamic Programming?

Which of the following problems can be efficiently solved using Dynamic Programming?

Which of the following is NOT a required characteristic for a problem to be solved using Dynamic Programming?

What is the output of the following code?
#include <iostream>
using namespace std;

int fibonacci(int n) {
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

int main() {
    cout << fibonacci(6);
    return 0;
}

What is the output of the following code?
#include <iostream>
using namespace std;

int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (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];
}

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    cout << knapsack(W, wt, val, n);
    return 0;
}

What is the output of the following code?
#include <iostream>
using namespace std;

int coinChange(int coins[], int n, int amount) {
    int dp[amount + 1];
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX;
        for (int j = 0; j < n; j++) {
            if (coins[j] <= i)
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    int coins[] = {1, 2, 5};
    int n = sizeof(coins)/sizeof(coins[0]);
    int amount = 11;
    cout << coinChange(coins, n, amount);
    return 0;
}

What is the output of the following code?
#include <iostream>
using namespace std;

int longestIncreasingSubsequence(int arr[], int n) {
    int dp[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] > maxLen)
            maxLen = dp[i];
    }
    return maxLen;
}

int main() {
    int arr[] = {3, 10, 2, 1, 20};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << longestIncreasingSubsequence(arr, n);
    return 0;
}

What is the output of the following code?
#include <iostream>
using namespace std;

int editDistance(string word1, string word2) {
    int m = word1.length();
    int n = word2.length();
    int dp[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = j;
            else if (j == 0)
                dp[i][j] = i;
            else if (word1[i-1] == word2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1]));
        }
    }
    return dp[m][n];
}

int main() {
    string word1 = "intention";
    string word2 = "execution";
    cout << editDistance(word1, word2);
    return 0;
}

What is the output of the following code?

```cpp
#include <iostream>
using namespace std;

int eggDrop(int eggs, int floors) {
    int dp[eggs + 1][floors + 1];
    for (int i = 1; i <= eggs; i++) {
        dp[i][1] = 1;
        dp[i][0] = 0;
    }
    for (int j = 1; j <= floors; j++)
        dp[1][j] = j;
    for (int i = 2; i <= eggs; i++) {
        for (int j = 2; j <= floors; j++) {
            dp[i][j] = INT_MAX;
            for (int x = 1; x <= j; x++) {
                int res = 1 + max(dp[i-1][x-1], dp[i][j-x]);
                dp[i][j] = min(dp[i][j], res);
            }
        }
    }
    return dp[eggs][floors];
}

int main() {
    int eggs = 2;
    int floors = 10;
    cout << eggDrop(eggs, floors);
    return 0;
}
```

What is the output of the following code?
```cpp
#include <iostream>
using namespace std;

int lps(string str) {
    int n = str.length();
    int dp[n][n];
    for (int i = 0; i < n; i++)
        dp[i][i] = 1;
    for (int cl = 2; cl <= n; cl++) {
        for (int i = 0; i < n - cl + 1; i++) {
            int j = i + cl - 1;
            if (str[i] == str[j] && cl == 2)
                dp[i][j] = 2;
            else if (str[i] == str[j])
                dp[i][j] = dp[i+1][j-1] + 2;
            else
                dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
        }
    }
    return dp[0][n-1];
}

int main() {
    string str = "BBABCBCAB";
    cout << lps(str);
    return 0;
}
```

What is the output of the following code?
```cpp
#include <iostream>
using namespace std;

int maxSumSubsequence(int arr[], int n) {
    int dp[n];
    for (int i = 0; i < n; i++) {
        dp[i] = arr[i];
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + arr[i])
                dp[i] = dp[j] + arr[i];
        }
    }
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] > maxSum)
            maxSum = dp[i];
    }
    return maxSum;
}

int main() {
    int arr[] = {1, 101, 2, 3, 100};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << maxSumSubsequence(arr, n);
    return 0;
}
```

What is the output of the following code?
```cpp
#include <iostream>
using namespace std;

int coinChange(int coins[], int n, int amount) {
    int dp[amount + 1];
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

int main() {
    int coins[] = {1, 2, 5};
    int n = sizeof(coins)/sizeof(coins[0]);
    int amount = 5;
    cout << coinChange(coins, n, amount);
    return 0;
}
```

What is the output of the following code?
```cpp
#include <iostream>
using namespace std;

int maxSubarraySum(int arr[], int n) {
    int maxSum = arr[0];
    int currMax = arr[0];
    for (int i = 1; i < n; i++) {
        currMax = max(arr[i], currMax + arr[i]);
        maxSum = max(maxSum, currMax);
    }
    return maxSum;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << maxSubarraySum(arr, n);
    return 0;
}
```