The text of the exercise is the following:
A builder is looking to build a row of N houses that can be of K different colours. He has a goal of minimizing cost while ensuring that no two neighbouring houses are not of the same colour.
Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth colour, return the minimum cost which achieves this goal.
Before solving the exercise, we can ask few questions to specify few aspects that might not be clear:
Can an house cost 0? No.
Can N > K or N < K ? Yes.
It is clear that finding the minimum iteratively for each house can return a local minimal solution but we are interested in the global minima.
import math
N = 6
K = 4
cost_matrix = [
[1 , 20, 34, 20],
[40, 10, 15, 30],
[50, 1, 20, 40],
[70, 80, 30, 1 ],
[1 , 60, 30, 40],
[70, 50, 1 , 20]
]
def find_house(row, col, tot, min_tot):
if row < N:
tot += cost_matrix[row][col]
for c in range(K):
if c != col:
min_tot = find_house(row+1, c, tot, min_tot)
else:
if min_tot > tot:
min_tot = tot
return min_tot
def main():
print ("Minimum value found:", find_house(0,0,0, math.inf)) #include<stdio.h>
#include<limits.h>
#define K 4
#define N 6
int cost_matrix[N][K] = {
{1 , 20, 34, 20},
{40, 10, 15, 30},
{50, 1, 20, 40},
{70, 80, 30, 1 },
{1 , 60, 30, 40},
{70, 50, 1 , 20}
};
int find_house(int row, int col, int tot, int min_tot)
{
if (row < N)
{
tot += cost_matrix[row][col];
for (int c=0; c<K; c++)
{
if (c != col)
min_tot = find_house(row+1,c, tot, min_tot);
}
}
else
{
if (min_tot > tot)
min_tot = tot;
}
return min_tot;
}
int main()
{
printf("Minimal cost: %d\n", find_house(0, 0, 0, INT_MAX));
return 0;
} public class BuildHouse {
static int N=6;
static int K=4;
static int cost_matrix[][] = {
{1 , 20, 34, 20},
{40, 10, 15, 30},
{50, 1, 20, 40},
{70, 80, 30, 1 },
{1 , 60, 30, 40},
{70, 50, 1 , 20}
};
public static void main(String[] args)
{
System.out.println("Minimum value found: "+ findHouse(0,0,0,Integer.MAX_VALUE));
}
static int findHouse(int row, int col, int tot, int min_tot)
{
if (row < N)
{
tot += cost_matrix[row][col];
for (int c=0; c<K; c++)
{
if (c != col)
min_tot = findHouse(row+1, c, tot, min_tot);
}
}
else
{
if (min_tot > tot)
min_tot = tot;
}
return min_tot;
}
}The function find_house is a recursive function that takes the row, col, tot and min_tot as input parameters.
The function transform the matrix into a tree and perform a kind of “depth-first” exploration returning the minimum of the total found.
row represents the row of the house.
col represents column of the house.
tot represents the total up to the reached node.
min_tot represents the minimum of the cost found up to that moment
The recursion stops when all the nodes have been explored.
Time complexity: \( O(N^K) \)
Space complexity: \( O(N^K) \)
