15 July 2023
Yet another fun day learning Dynamic Programming. I'll be sharing the questions I did.
Note: The questions are from my course module Coding Ninjas
Number of Balanced Binary Trees
Given an integer h, find the possible number of balanced binary trees of height h. You just need to return the count of possible binary trees which are balanced.
This number can be huge, so, return output modulus 10^9 + 7.
Input Format:
The first and only line of input contains an integer, that denotes the value of h. Here, h is the height of the tree.
Output Format:
The first and only line of output contains the count of balanced binary trees modulus 10^9 + 7.
Constraints:
1 <= h <= 24
Time Limit: 1 sec
Sample Input 1:
3
Sample Output 1:
15
Sample Input 2:
4
Sample Output 2:
315
My solution:
- Brute Force (Recursive)
int balancedBTs(int n) {
// Write your code here
int num = 1e9+7;
if(n<=1){
return 1;
}
long long int a = balancedBTs(n-1);
long long int b = balancedBTs(n-2);
long long int temp1 = (a*a)%num;
long long int temp2 = (2*a*b)%num;
return (temp1+temp2)%num;
}
- Using Memoization
int helper(int n, long long int* arr){
int num = 1e9+7;
if(n<=1){
return 1;
}
if(arr[n]!=-1){
return arr[n];
}
long long int a = helper(n-1,arr);
long long int b = helper(n-2,arr);
long long int temp1 = (a*a)%num;
long long int temp2 = (2*a*b)%num;
arr[n] = (temp1+temp2)%num;
return arr[n];
}
int balancedBTs(int n) {
// Write your code here
long long int arr[n+1];
for(long long int i=0;i<=n;i++){
arr[i] = -1;
}
return helper(n,arr);
}
- Using Dynamic Programming
#include <cmath>
int balancedBTs(int h) {
// Write your code here
long long int arr[h+1];
int mod = 1e9+7;
arr[0] = 1;
arr[1] = 1;
for(int i=2;i<=h;i++){
long long int a = arr[i-1];
long long int b = arr[i-2];
long long int temp1 = (a*a)%mod;
long long int temp2= (2*a*b)%mod;
arr[i] = (temp1+temp2)%mod;
}
return arr[h];
}
Min Cost Path
An integer matrix of size (M x N) has been given. Find out the minimum cost to reach from the cell (0, 0) to (M - 1, N - 1).
From a cell (i, j), you can move in three directions:
1. ((i + 1), j) which is, "down"
2. (i, (j + 1)) which is, "to the right"
3. ((i+1), (j+1)) which is, "to the diagonal"
The cost of a path is defined as the sum of each cell's values through which the route passes.
Input Format:
The first line of the test case contains two integer values, 'M' and 'N', separated by a single space. They represent the 'rows' and 'columns' respectively, for the two-dimensional array/list.
The second line onwards, the next 'M' lines or rows represent the ith row values.
Each of the ith row constitutes 'N' column values separated by a single space.
Output Format:
Print the minimum cost to reach the destination.
Constraints:
1 <= M <= 10 ^ 2
1 <= N <= 10 ^ 2
Time Limit: 1 sec
Sample Input 1:
3 4
3 4 1 2
2 1 8 9
4 7 8 1
Sample Output 1:
13
Sample Input 2:
3 4
10 6 9 0
-23 8 9 90
-200 0 89 200
Sample Output 2:
76
Sample Input 3:
5 6
9 6 0 12 90 1
2 7 8 5 78 6
1 6 0 5 10 -4
9 6 2 -10 7 4
10 -2 0 5 5 7
Sample Output 3:
18
My solution:
- Brute Force (Recursive)
int minCostPathHelper(int **input,int m,int n,int i,int j){
if(i>=m || j>=n){
return INT_MAX;
}
if(i==m-1 && j==n-1){
return input[i][j];
}
int a = minCostPathHelper(input, m, n, i+1, j);
int b = minCostPathHelper(input, m, n, i, j+1);
int c = minCostPathHelper(input, m, n, i+1, j+1);
return min(a,min(b,c))+input[i][j];
}
int minCostPath(int **input, int m, int n)
{
//Write your code here
return minCostPathHelper(input, m, n, 0, 0);
}
- Using Memoization
int minCostPathHelper(int **input,int m,int n,int i,int j,int **arr){
if(i>=m || j>=n){
return INT_MAX;
}
if(i==m-1 && j==n-1){
return input[i][j];
}
if(arr[i][j]!=-1){
return arr[i][j];
}
int a = minCostPathHelper(input, m, n, i+1, j,arr);
int b = minCostPathHelper(input, m, n, i, j+1,arr);
int c = minCostPathHelper(input, m, n, i+1, j+1,arr);
arr[i][j] = min(a,min(b,c))+input[i][j];
return arr[i][j];
}
int minCostPath(int **input, int m, int n)
{
//Write your code here
int **arr;
arr = new int *[m];
for (int i = 0; i < m; i++)
{
arr[i] = new int[n];
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
arr[i][j]=-1;
}
}
return minCostPathHelper(input, m, n, 0, 0,arr);
}
- Using Dynamic Programming
int minCostPath(int **input, int m, int n)
{
//Write your code here
int minSum = input[0][0];
int **output = new int*[m];
for(int i=0;i<m;i++){
output[i] = new int[n];
}
output[m-1][n-1] = input[m-1][n-1];
for(int j=n-2;j>=0;j--){
output[m-1][j] = output[m-1][j+1]+input[m-1][j];
}
for(int i=m-2;i>=0;i--){
output[i][n-1] = output[i+1][n-1]+input[i][n-1];
}
for(int i=m-2;i>=0;i--){
for(int j=n-2;j>=0;j--){
int a = min(output[i+1][j],min(output[i][j+1],output[i+1][j+1]));
output[i][j] = a+input[i][j];
}
}
return output[0][0];
}