Paint House IIl

In this approach, we will use a recursive function to find the minimum cost required. We will define a function HELPER(‘IDX’,’ TARGET’,’LAST_COLOR’,’ HOUSES’,’ COST’).IDX is the current index of ‘HOUSE,’ and ‘TARGET’ is the remaining number of neighborhood groups and ‘LAST_COLOR’ is the color of the last house. We will try each color for the houses which are not painted yet (‘HOUSES’[IDX] == 0).

Algorithm:

• Defining HELPER(‘IDX’,’ TARGET’,’LAST_COLOR’,’ HOUSES’,’ COST’) function.
  • If ‘IDX’ == length of ‘HOUSES’ and ‘TARGET’ is equal to 0:
    • Return 0 . (All houses painted and groups is equal to ‘M’).
  • If ‘IDX’ >= length of ‘HOUSES’ OR ‘TARGET’ is less than 0:
    • Return INT_MAX (Conditions not satisfied).
  • If ‘HOUSES[‘IDX’], not equal 0:
    • The house is already painted.
    • If ‘HOUSES[‘IDX’] is not equal to LAST_COLOR’:
      • A new neighborhood group.
      • Set ‘TARGET’ as ‘TARGET’ -1.
    • Return  ‘HELPER(‘IDX’ + 1,’TARGET’,HOUSES[‘IDX’],’HOUSES’,’COST’).
  • Set ‘ANS’ as INT_MAX.
  • Trying each color for the uncolored house.
  • For each index i in range 1 to the size of ‘COST[‘IDX’]’, do the following:
    • If  i is equal to ‘LAST_COLOR’:
      • Set ‘NEW_TARGET’ as ‘TARGET’.
    • Else:
      • Set ‘NEW_TARGET’ as ‘TARGET’ -1 (A new neighborhood group.)
    • Set ‘ANS’ as the minimum of ‘ANS’ and COST[‘IDX’][i -1] + ‘HELPER(‘IDX’ + 1, ’NEW_TARGET’, i, ’HOUSES’, ’COST’).
  • Return ‘ANS’.

• Set ‘ANS’ as ‘HELPER(‘0,’M’0,’HOUSES’,’ COST’).
• If ‘ANS’ is ‘INT_MAX’.
  • Return -1. (Impossible to paint to fulfill the condition.)
• Return ‘ANS’.

In the previous approach, we used a recursive function to find the answer.

In this approach, we will use dynamic programming to formulate the answer. We will use the same function 'HELPER'(), but we will also use memoization and store the values in the ‘DP’ table to use the precomputed values.

Algorithm:

• Defining HELPER(‘IDX’,’ TARGET’,’LAST_COLOR’,’ HOUSES’,’ COST’, ‘DP’) function.
  • If ‘IDX’ == length of ‘HOUSES’ and ‘TARGET’ is equal to 0:
    • Return 0. (All houses painted and groups is equal to ‘M’).
  • If ‘IDX’ >= length of ‘HOUSES’ OR ‘TARGET’ is less than 0:
    • Return INT_MAX (Conditions not satisfied).
  • If DP[‘IDX’][‘TARGET’][‘LAST_COLOR’] is not equal to -1:
    • Value for this state is already computed.
    • Return DP[‘IDX’][‘TARGET’][‘LAST_COLOR’].
  • If ‘HOUSES[‘IDX’], not equal 0:
    • The house is already painted.
    • If ‘HOUSES[‘IDX’] is not equal to LAST_COLOR’:
      • A new neighborhood group.
      • Set ‘TARGET’ as ‘TARGET’ -1.
    • Return  ‘HELPER(‘IDX’ + 1,’TARGET’,HOUSES[‘IDX’],’HOUSES’,’COST’, ‘DP’).
  • Set ‘ANS’ as INT_MAX.
  • Trying each color for the uncolored house.
  • For each index k in range 1 to the size of ‘COST[‘IDX’]’, do the following:
    • If  k is equal to ‘LAST_COLOR’:
      • Set ‘NEW_TARGET’ as ‘TARGET’.
    • Else:
      • Set ‘NEW_TARGET’ as ‘TARGET’ -1 (A new neighborhood group.)
    • Set ‘ANS’ as the minimum of ‘ANS’ and COST[‘IDX’][k -1] + ‘HELPER(‘IDX’ + 1, ’NEW_TARGET’, k, ’HOUSES’, ’COST’, ‘DP’).
  • Return ‘ANS’.
• Initialize a ‘DP’ table of size N*M*K.
• Set all values of the ‘DP’ table as -1.
• Set ‘ANS’ as  ‘HELPER(‘0,’M’0,’HOUSES’,’COST’, ‘DP’).
• If ‘ANS’ is ‘INT_MAX’.
  • Return -1. (Impossible to paint to fulfill the condition.)
• Return ‘ANS’.

In this approach, we will build up a ‘DP’ table of size ‘DP’[‘N’+1][‘K’+1][‘M’+1].DP[i][j][k] will denote the minimum cost for the first i houses, and i’th house is painted with j’th color, and there are k neighborhood groups. We will iterate over all the ‘DP’ states and find their value using the following conditions:

1. If ‘HOUSES’[i] is not 0, it means that the house is already painted, so the color of the previous house is deterministic whether it will form a new neighborhood group or not.

2. If ‘HOUSES[i]’ is 0, we will try all colors for this building and pick the color which gives the total minimum cost. 

At last, we will iterate over all color k and find the minimum among DP[‘N’-1][k][‘M’] for all ‘k’.

Algorithm:

• Declare a 3-D ‘DP’ array of size ‘DP’[‘N’+1][‘K’+1][‘M’+1] to store the values.
• Set all values of ‘DP’ as INT_MAX.
• If ‘HOUSES[0]’ is not equal to 0:
  • Set ‘DP[0][‘HOUSES[0]][1]’ as 0 (Already painted,no cost).
• Else:
  • Trying each color for the first house.
  • For i in range 1 to K,do the following:
    • Set DP[0][i][1] as COST[0][i-1].
• For k in range 1 to ‘M’, do the following:
  • For i in range 1 to ‘N-1’, do the following:
    • If ‘HOUSES’[i-1] is not 0:
      • Set ‘CUR_COLOR’ as ‘HOUSES[i-1]’.
      • Iterate over previous colors and find the minimum cost:
      • For ‘C’ in range 1 to ‘K’:
        • If ‘C’ is equal to ‘CUR_COLOR’:
          • Set ‘DP’[i][CUR_COLOR][k] as minimum of DP’[i][CUR_COLOR][k] and DP[i-1][C][K].
        • Else:
          • Set DP’[i][CUR_COLOR][k] as minimum of DP’[i][CUR_COLOR][k] and DP[i-1][C][K-1].
    • Else:
      • ‘C1’ is for the current color, and ‘C2’ is for the previous color.
      • For ‘C1’ in range 1 to  K:
        • For ‘C2’ in range 1 to K:
          • If ‘C1’ is equal to ‘C2’:
            • Set DP[i][C1][k] as minimum of DP[i][C1][k] and ( DP[i-1][C2][k] + ‘COST[i-1][C1-1]’.
          • Else:
            • Set DP[i][C1][k] as minimum of DP[i][C1][k] and ( DP[i-1][C2][k-1] + ‘COST[i-1][C1-1]’.
• Set ‘ANS’ as INT_MAX.
• For c in range 1 to K:
  • Set ‘ANS’ as the minimum of ‘ANS’ and DP[N][c][M].
• If ‘ANS’ is ‘INT_MAX’.
  • Return -1. (Impossible to paint to fulfill the condition.)
• Return ‘ANS’.