Test: Dynamic Programming - 1 - Software Development MCQ

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;
}
```