Day 15 (30 Days of Code)

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];

}