DP - Sequence Adjacent Element

Algorithms
dp
Catalogue
  1. 1. 256. Paint House
  2. 2. 265. Paint House II
  3. 3. 276. Paint Fence
  4. 4. 198. House Robber
  5. 5. 213. House Robber II

256. Paint House

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def minCost(self, costs):
        if not costs:
            return 0

        n = len(costs)
        dp = [[0] * 3 for _ in range(n)]
        for j in range(3):
            dp[0][j] = costs[0][j]

        for i in range(1, n):
            for j in range(3):
                dp[i][j] = costs[i][j] + min(dp[i-1][j-1], dp[i-1][j-2])
        return min(dp[-1])

265. Paint House II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def minCostII(self, costs):
        if not costs:
            return 0

        n, k = len(costs), len(costs[0])
        dp = [[0] * k for _ in range(n)]
        for j in range(k):
            dp[0][j] = costs[0][j]

        for i in range(1, n):
            for j in range(k):
                dp[i][j] = costs[i][j] + min(dp[i-1][:j] + dp[i-1][j+1:])
        return min(dp[-1])

276. Paint Fence

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def numWays(self, n, k):
        if n == 0 or k == 0:
            return 0

        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = k
        dp[0][1] = 0
        for i in range(1, n):
            dp[i][0] = (dp[i-1][0] + dp[i-1][1]) * (k-1)
            dp[i][1] = dp[i-1][0]
        return sum(dp[-1])

198. House Robber

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def rob(self, nums):
        if not nums:
            return 0

        n = len(nums)
        dp1 = [0] * n # Stole
        dp2 = [0] * n # Not Stole
        dp1[0] = nums[0]
        for i in range(1, n):
            dp1[i] = dp2[i-1] + nums[i]
            dp2[i] = max(dp1[i-1], dp2[i-1])
        return max(dp1[-1], dp2[-1])

213. House Robber II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def rob(self, nums):
        n = len(nums)
        if n <= 1:
            return sum(nums)

        prev = rob1 = 0
        for num in nums[1:]:
            temp = rob1
            rob1 = max(prev + num, rob1)
            prev = temp

        prev = rob2 = 0
        for num in nums[:-1]:
            temp = rob2
            rob2 = max(prev + num, rob2)
            prev = temp

        return max(rob1, rob2)
Share