Problem statement

https://binarysearch.com/problems/Spiky-Plants/

Solution

We can notice, that in the end position will be for every plant we have heights H[i], H[i] + 1 or H[i] + 2, no more. So, we can now just run dp with states dp[i, H] the minimum cost we pay when we reached i-th plant and heigth H. Alternative way is to use layer by layer dp, where we keep only values for layer i.

Complexity

It is O(n*9) for time and O(3) for space.

Code

class Solution:
    def solve(self, H, C):
        dp = {0: 0}
        n = len(H)
        for i in range(n):
            dp2 = defaultdict(lambda: float("inf"))
            for h1 in dp:
                for h2 in H[i], H[i] + 1, H[i] + 2:
                    if h1 != h2:
                        dp2[h2] = min(dp2[h2], dp[h1] + (h2 - H[i]) * C[i])
            dp = dp2
        return min(dp.values())