Paint House 3

Problem

There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that have been painted last summer should not be painted again.

A neighborhood is a maximal group of continuous houses that are painted with the same color.

For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}].

Given an array houses, an m x n matrix cost and an integer target where:

houses[i]: is the color of the house i, and 0 if the house is not painted yet.
cost[i][j]: is the cost of paint the house i with the color j + 1.

Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods. If it is not possible, return -1.

Examples

Example 1:

1
2
3
4
5
6
7


Input:
houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output:
 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

Example 2:

1
2
3
4
5
6
7


Input:
houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output:
 11
Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. 
Cost of paint the first and last house (10 + 1) = 11.

Example 3:

1
2
3
4
5


Input:
houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
Output:
 -1
Explanation: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.

Solution

Method 1 - Top Down DP

Intuition

This problem can be solved using backtracking with memoization. The key idea is to fill unpainted houses (slots with value 0) with available colors, aiming to form exactly target neighborhoods at minimum cost. At each step, we track the current neighborhood count and previous color, and make choices that either continue the current neighborhood or start a new one. Memoization helps avoid redundant calculations for repeated subproblems.

Approach

Use recursion to try all possible ways to paint each house, keeping track of:
- The current house index (idx)
- The number of neighborhoods left to form (target)
- The color of the previous house (prevIdx)
For each house:
- If already painted, check if it starts a new neighborhood (color differs from previous), and recurse to the next house.
- If not painted, try all possible colors, calculate the cost, and recurse, updating the neighborhood count if the color changes.
The recursion ends when all houses are processed:
- If the required number of neighborhoods is formed (target == 0), return the cost.
- Otherwise, return an impossible value.
Memoize results for each state (idx, target, prevIdx) to avoid recomputation.

Recursion Tree

Complexity

⏰ Time complexity: O(m * n * target * n) — For each house (m), we try every color (n) and every possible remaining target (target), and for each, we may try all colors again in recursion. Memoization ensures each state (idx, target, prevColor) is computed only once.
🧺 Space complexity: O(m * n * target) — The memoization table stores results for each combination of house index, target, and previous color.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
	int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
		vector<vector<vector<long>>> memo(m, vector<vector<long>>(target+1, vector<long>(n+1, -1)));
		function<long(int,int,int)> dfs = [&](int idx, int t, int prev) -> long {
			if (idx == m) return t == 0 ? 0 : INT_MAX;
			if (t < 0) return INT_MAX;
			if (memo[idx][t][prev] != -1) return memo[idx][t][prev];
			long ans = INT_MAX;
			if (houses[idx] == 0) {
				for (int color = 1; color <= n; ++color) {
					long c = cost[idx][color-1] + dfs(idx+1, t-(color!=prev), color);
					ans = min(ans, c);
				}
			} else {
				ans = dfs(idx+1, t-(houses[idx]!=prev), houses[idx]);
			}
			return memo[idx][t][prev] = ans;
		};
		long res = dfs(0, target, 0);
		return res == INT_MAX ? -1 : (int)res;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


type Solution struct{}
func minCost(houses []int, cost [][]int, m, n, target int) int {
	memo := make([][][]int64, m)
	for i := range memo {
		memo[i] = make([][]int64, target+1)
		for j := range memo[i] {
			memo[i][j] = make([]int64, n+1)
			for k := range memo[i][j] {
				memo[i][j][k] = -1
			}
		}
	}
	var dfs func(idx, t, prev int) int64
	dfs = func(idx, t, prev int) int64 {
		if idx == m {
			if t == 0 { return 0 }
			return 1<<31 - 1
		}
		if t < 0 { return 1<<31 - 1 }
		if memo[idx][t][prev] != -1 { return memo[idx][t][prev] }
		ans := int64(1<<31 - 1)
		if houses[idx] == 0 {
			for color := 1; color <= n; color++ {
				c := int64(cost[idx][color-1]) + dfs(idx+1, t-(color!=prev), color)
				if c < ans { ans = c }
			}
		} else {
			ans = dfs(idx+1, t-(houses[idx]!=prev), houses[idx])
		}
		memo[idx][t][prev] = ans
		return ans
	}
	res := dfs(0, target, 0)
	if res == 1<<31-1 { return -1 }
	return int(res)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
	public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
		long[][][] memo = new long[m][target + 1][n + 1];
		for (int i = 0; i < m; i++)
			for (int j = 0; j < target + 1; j++)
				Arrays.fill(memo[i][j], -1);
		long ans = dfs(houses, cost, m, n, target, 0, 0, memo);
		return ans == Integer.MAX_VALUE ? -1 : (int)ans;
	}
	private long dfs(int[] houses, int[][] cost, int m, int n, int target, int idx, int prevIdx, long[][][] memo) {
		if (idx == m) return target == 0 ? 0 : Integer.MAX_VALUE;
		if (target < 0) return Integer.MAX_VALUE;
		if (memo[idx][target][prevIdx] != -1) return memo[idx][target][prevIdx];
		long ans = Integer.MAX_VALUE;
		if (houses[idx] == 0) {
			for (int j = 1; j <= n; j++) {
				ans = Math.min(ans, cost[idx][j - 1] + dfs(houses, cost, m, n, target - ((j != prevIdx) ? 1 : 0), idx + 1, j, memo));
			}
		} else {
			ans = dfs(houses, cost, m, n, target - ((houses[idx] != prevIdx) ? 1 : 0), idx + 1, houses[idx], memo);
		}
		memo[idx][target][prevIdx] = ans;
		return ans;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
	fun minCost(houses: IntArray, cost: Array<IntArray>, m: Int, n: Int, target: Int): Int {
		val memo = Array(m) { Array(target+1) { LongArray(n+1) { -1L } } }
		fun dfs(idx: Int, t: Int, prev: Int): Long {
			if (idx == m) return if (t == 0) 0L else Long.MAX_VALUE
			if (t < 0) return Long.MAX_VALUE
			if (memo[idx][t][prev] != -1L) return memo[idx][t][prev]
			var ans = Long.MAX_VALUE
			if (houses[idx] == 0) {
				for (color in 1..n) {
					val c = cost[idx][color-1] + dfs(idx+1, t - if (color != prev) 1 else 0, color)
					ans = minOf(ans, c)
				}
			} else {
				ans = dfs(idx+1, t - if (houses[idx] != prev) 1 else 0, houses[idx])
			}
			memo[idx][t][prev] = ans
			return ans
		}
		val res = dfs(0, target, 0)
		return if (res == Long.MAX_VALUE) -1 else res.toInt()
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
	def minCost(self, houses: list[int], cost: list[list[int]], m: int, n: int, target: int) -> int:
		memo = [[[None for _ in range(n+1)] for _ in range(target+1)] for _ in range(m)]
		def dfs(idx: int, t: int, prev: int) -> int:
			if idx == m:
				return 0 if t == 0 else float('inf')
			if t < 0:
				return float('inf')
			if memo[idx][t][prev] is not None:
				return memo[idx][t][prev]
			ans = float('inf')
			if houses[idx] == 0:
				for color in range(1, n+1):
					c = cost[idx][color-1] + dfs(idx+1, t-(color!=prev), color)
					ans = min(ans, c)
			else:
				ans = dfs(idx+1, t-(houses[idx]!=prev), houses[idx])
			memo[idx][t][prev] = ans
			return ans
		res = dfs(0, target, 0)
		return -1 if res == float('inf') else res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


impl Solution {
	pub fn min_cost(houses: Vec<i32>, cost: Vec<Vec<i32>>, m: i32, n: i32, target: i32) -> i32 {
		let m = m as usize;
		let n = n as usize;
		let target = target as usize;
		let mut memo = vec![vec![vec![-1i64; n+1]; target+1]; m];
		fn dfs(idx: usize, t: usize, prev: usize, houses: &Vec<i32>, cost: &Vec<Vec<i32>>, m: usize, n: usize, target: usize, memo: &mut Vec<Vec<Vec<i64>>>) -> i64 {
			if idx == m { return if t == 0 { 0 } else { i64::MAX }; }
			if t > target { return i64::MAX; }
			if memo[idx][t][prev] != -1 { return memo[idx][t][prev]; }
			let mut ans = i64::MAX;
			if houses[idx] == 0 {
				for color in 1..=n {
					let c = cost[idx][color-1] as i64 + dfs(idx+1, t + if color != prev { 1 } else { 0 }, color, houses, cost, m, n, target, memo);
					if c < ans { ans = c; }
				}
			} else {
				ans = dfs(idx+1, t + if houses[idx] as usize != prev { 1 } else { 0 }, houses[idx] as usize, houses, cost, m, n, target, memo);
			}
			memo[idx][t][prev] = ans;
			ans
		}
		let res = dfs(0, 0, 0, &houses, &cost, m, n, target, &mut memo);
		if res == i64::MAX { -1 } else { res as i32 }
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
	minCost(houses: number[], cost: number[][], m: number, n: number, target: number): number {
		const memo: (number | undefined)[][][] = Array.from({length: m}, () => Array.from({length: target+1}, () => Array(n+1)));
		const dfs = (idx: number, t: number, prev: number): number => {
			if (idx === m) return t === 0 ? 0 : Infinity;
			if (t < 0) return Infinity;
			if (memo[idx][t][prev] !== undefined) return memo[idx][t][prev]!;
			let ans = Infinity;
			if (houses[idx] === 0) {
				for (let color = 1; color <= n; color++) {
					const c = cost[idx][color-1] + dfs(idx+1, t-(color!==prev?1:0), color);
					ans = Math.min(ans, c);
				}
			} else {
				ans = dfs(idx+1, t-(houses[idx]!==prev?1:0), houses[idx]);
			}
			memo[idx][t][prev] = ans;
			return ans;
		};
		const res = dfs(0, target, 0);
		return res === Infinity ? -1 : res;
	}
}

Method 2 - Bottom up DP

Intuition

This method uses dynamic programming to iteratively build up solutions for each house, color, and neighborhood count. Instead of recursion, we fill a 3D DP table where each entry represents the minimum cost to paint up to a certain house with a given color and number of neighborhoods. By considering all possible transitions from previous states, we ensure that all combinations are explored efficiently.

Approach

Define a 3D DP array dp[i][j][t] where:
- i is the current house index
- j is the color being considered for house i
- t is the number of neighborhoods formed so far
- Each entry stores the minimum cost to reach that state, or -1 if impossible.
Initialize the DP array:
- For the first house, set the cost for each possible color and one neighborhood.
Iterate over each house from left to right:
- For each possible number of neighborhoods and color, update the DP value by considering all valid previous color choices.
- If the house is already painted, only consider its color; otherwise, try all colors.
- If the color matches the previous house, the neighborhood count stays the same; otherwise, it increases by one.
- Accumulate the cost accordingly.
After filling the DP table, the answer is the minimum cost among all color choices for the last house with exactly target neighborhoods.
If no valid solution exists, return -1.

Complexity

⏰ Time complexity: O(m * n^2 * target) — For each house (m), color (n), and target (target), we try every previous color (n), leading to an extra factor of n in the innermost loop.
🧺 Space complexity: O(m * n * target) — The DP table stores results for each combination of house, color, and target.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
public:
	int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
		vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(target+1, -1)));
		for (int i = 0; i < n; ++i) {
			if (houses[0] == 0) dp[0][i][1] = cost[0][i];
			else if (houses[0] == i+1) dp[0][i][1] = 0;
		}
		for (int i = 1; i < m; ++i) {
			for (int t = 1; t <= target && t <= i+1; ++t) {
				for (int j = 0; j < n; ++j) {
					if (houses[i] != 0 && houses[i] != j+1) continue;
					int costToPaint = houses[i] == j+1 ? 0 : cost[i][j];
					for (int k = 0; k < n; ++k) {
						if (j == k && dp[i-1][k][t] != -1) {
							int val = costToPaint + dp[i-1][k][t];
							dp[i][j][t] = dp[i][j][t] == -1 ? val : min(dp[i][j][t], val);
						} else if (j != k && dp[i-1][k][t-1] != -1) {
							int val = costToPaint + dp[i-1][k][t-1];
							dp[i][j][t] = dp[i][j][t] == -1 ? val : min(dp[i][j][t], val);
						}
					}
				}
			}
		}
		int ans = -1;
		for (int i = 0; i < n; ++i) {
			if (dp[m-1][i][target] != -1) ans = ans == -1 ? dp[m-1][i][target] : min(ans, dp[m-1][i][target]);
		}
		return ans;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


type Solution struct{}
func minCost(houses []int, cost [][]int, m, n, target int) int {
	dp := make([][][]int, m)
	for i := range dp {
		dp[i] = make([][]int, n)
		for j := range dp[i] {
			dp[i][j] = make([]int, target+1)
			for k := range dp[i][j] {
				dp[i][j][k] = -1
			}
		}
	}
	for i := 0; i < n; i++ {
		if houses[0] == 0 {
			dp[0][i][1] = cost[0][i]
		} else if houses[0] == i+1 {
			dp[0][i][1] = 0
		}
	}
	for i := 1; i < m; i++ {
		for t := 1; t <= target && t <= i+1; t++ {
			for j := 0; j < n; j++ {
				if houses[i] != 0 && houses[i] != j+1 {
					continue
				}
				costToPaint := 0
				if houses[i] != j+1 {
					costToPaint = cost[i][j]
				}
				for k := 0; k < n; k++ {
					if j == k && dp[i-1][k][t] != -1 {
						val := costToPaint + dp[i-1][k][t]
						if dp[i][j][t] == -1 || val < dp[i][j][t] {
							dp[i][j][t] = val
						}
					} else if j != k && t > 0 && dp[i-1][k][t-1] != -1 {
						val := costToPaint + dp[i-1][k][t-1]
						if dp[i][j][t] == -1 || val < dp[i][j][t] {
							dp[i][j][t] = val
						}
					}
				}
			}
		}
	}
	ans := -1
	for i := 0; i < n; i++ {
		if dp[m-1][i][target] != -1 {
			if ans == -1 || dp[m-1][i][target] < ans {
				ans = dp[m-1][i][target]
			}
		}
	}
	return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution {
	public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
		int[][][] dp = new int[m][n][target+1];
		for(int i = 0; i < m; i++)
			for(int j = 0; j < n; j++)
				for(int k=0; k <= target; k++)
					dp[i][j][k] = -1;
		for(int i = 0; i < n; i++) {
			if (houses[0] == 0) dp[0][i][1]=cost[0][i];
			else if (houses[0] == i+1) dp[0][i][1] = 0;
		}
		for(int i = 1; i < m; i++) {
			for(int t = 1; t <= target && t <= i+1; t++) {
				for(int j = 0; j < n; j++) {
					if (houses[i] != 0 && houses[i] != j+1) continue;
					int costToPaint = houses[i]==j+1 ? 0 : cost[i][j];
					for(int k = 0; k < n; k++) {
						if (j == k && dp[i-1][k][t] != -1) {
							int val = costToPaint + dp[i-1][k][t];
							dp[i][j][t] = dp[i][j][t] == -1 ? val : Math.min(dp[i][j][t], val);
						}
						else if (j != k && dp[i-1][k][t-1] != -1) {
							int val = costToPaint + dp[i-1][k][t-1];
							dp[i][j][t] = dp[i][j][t] == -1 ? val : Math.min(dp[i][j][t], val);
						}
					}
				}
			}
		}
		int ans = -1;
		for(int i = 0; i < n; i++) {
			if (dp[m-1][i][target] != -1) ans = ans == -1 ? dp[m-1][i][target] : Math.min(ans,dp[m-1][i][target]);
		}
		return ans;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
	fun minCost(houses: IntArray, cost: Array<IntArray>, m: Int, n: Int, target: Int): Int {
		val dp = Array(m) { Array(n) { IntArray(target+1) { -1 } } }
		for (i in 0 until n) {
			if (houses[0] == 0) dp[0][i][1] = cost[0][i]
			else if (houses[0] == i+1) dp[0][i][1] = 0
		}
		for (i in 1 until m) {
			for (t in 1..target.coerceAtMost(i+1)) {
				for (j in 0 until n) {
					if (houses[i] != 0 && houses[i] != j+1) continue
					val costToPaint = if (houses[i] == j+1) 0 else cost[i][j]
					for (k in 0 until n) {
						if (j == k && dp[i-1][k][t] != -1) {
							val v = costToPaint + dp[i-1][k][t]
							dp[i][j][t] = if (dp[i][j][t] == -1) v else minOf(dp[i][j][t], v)
						} else if (j != k && t > 0 && dp[i-1][k][t-1] != -1) {
							val v = costToPaint + dp[i-1][k][t-1]
							dp[i][j][t] = if (dp[i][j][t] == -1) v else minOf(dp[i][j][t], v)
						}
					}
				}
			}
		}
		var ans = -1
		for (i in 0 until n) {
			if (dp[m-1][i][target] != -1) ans = if (ans == -1) dp[m-1][i][target] else minOf(ans, dp[m-1][i][target])
		}
		return ans
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
	def minCost(self, houses: list[int], cost: list[list[int]], m: int, n: int, target: int) -> int:
		dp = [[[-1 for _ in range(target+1)] for _ in range(n)] for _ in range(m)]
		for i in range(n):
			if houses[0] == 0:
				dp[0][i][1] = cost[0][i]
			elif houses[0] == i+1:
				dp[0][i][1] = 0
		for i in range(1, m):
			for t in range(1, min(target, i+1)+1):
				for j in range(n):
					if houses[i] != 0 and houses[i] != j+1:
						continue
					costToPaint = 0 if houses[i] == j+1 else cost[i][j]
					for k in range(n):
						if j == k and dp[i-1][k][t] != -1:
							val = costToPaint + dp[i-1][k][t]
							dp[i][j][t] = val if dp[i][j][t] == -1 else min(dp[i][j][t], val)
						elif j != k and t > 0 and dp[i-1][k][t-1] != -1:
							val = costToPaint + dp[i-1][k][t-1]
							dp[i][j][t] = val if dp[i][j][t] == -1 else min(dp[i][j][t], val)
		ans = -1
		for i in range(n):
			if dp[m-1][i][target] != -1:
				ans = dp[m-1][i][target] if ans == -1 else min(ans, dp[m-1][i][target])
		return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


impl Solution {
	pub fn min_cost(houses: Vec<i32>, cost: Vec<Vec<i32>>, m: i32, n: i32, target: i32) -> i32 {
		let m = m as usize;
		let n = n as usize;
		let target = target as usize;
		let mut dp = vec![vec![vec![-1; target+1]; n]; m];
		for i in 0..n {
			if houses[0] == 0 {
				dp[0][i][1] = cost[0][i];
			} else if houses[0] == (i+1) as i32 {
				dp[0][i][1] = 0;
			}
		}
		for i in 1..m {
			for t in 1..=target.min(i+1) {
				for j in 0..n {
					if houses[i] != 0 && houses[i] != (j+1) as i32 { continue; }
					let cost_to_paint = if houses[i] == (j+1) as i32 { 0 } else { cost[i][j] };
					for k in 0..n {
						if j == k && dp[i-1][k][t] != -1 {
							let val = cost_to_paint + dp[i-1][k][t];
							dp[i][j][t] = if dp[i][j][t] == -1 { val } else { dp[i][j][t].min(val) };
						} else if j != k && t > 0 && dp[i-1][k][t-1] != -1 {
							let val = cost_to_paint + dp[i-1][k][t-1];
							dp[i][j][t] = if dp[i][j][t] == -1 { val } else { dp[i][j][t].min(val) };
						}
					}
				}
			}
		}
		let mut ans = -1;
		for i in 0..n {
			if dp[m-1][i][target] != -1 {
				ans = if ans == -1 { dp[m-1][i][target] } else { ans.min(dp[m-1][i][target]) };
			}
		}
		ans
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
	minCost(houses: number[], cost: number[][], m: number, n: number, target: number): number {
		const dp: number[][][] = Array.from({length: m}, () => Array.from({length: n}, () => Array(target+1).fill(-1)));
		for (let i = 0; i < n; i++) {
			if (houses[0] === 0) dp[0][i][1] = cost[0][i];
			else if (houses[0] === i+1) dp[0][i][1] = 0;
		}
		for (let i = 1; i < m; i++) {
			for (let t = 1; t <= target && t <= i+1; t++) {
				for (let j = 0; j < n; j++) {
					if (houses[i] !== 0 && houses[i] !== j+1) continue;
					const costToPaint = houses[i] === j+1 ? 0 : cost[i][j];
					for (let k = 0; k < n; k++) {
						if (j === k && dp[i-1][k][t] !== -1) {
							const val = costToPaint + dp[i-1][k][t];
							dp[i][j][t] = dp[i][j][t] === -1 ? val : Math.min(dp[i][j][t], val);
						} else if (j !== k && t > 0 && dp[i-1][k][t-1] !== -1) {
							const val = costToPaint + dp[i-1][k][t-1];
							dp[i][j][t] = dp[i][j][t] === -1 ? val : Math.min(dp[i][j][t], val);
						}
					}
				}
			}
		}
		let ans = -1;
		for (let i = 0; i < n; i++) {
			if (dp[m-1][i][target] !== -1) ans = ans === -1 ? dp[m-1][i][target] : Math.min(ans, dp[m-1][i][target]);
		}
		return ans;
	}
}

Problem#

Examples#

Solution#

Method 1 - Top Down DP#

Intuition#

Approach#

Complexity#

Code#

Method 2 - Bottom up DP#

Intuition#

Approach#

Complexity#

Code#

Problem

Examples

Solution

Method 1 - Top Down DP

Intuition

Approach

Complexity

Code

Method 2 - Bottom up DP

Intuition

Approach

Complexity

Code