dp_caching_1.go

const (
    INF = int(1e9)
)

func maxProfit(prices []int) int {
    cache := createCache(len(prices), -1)
    return run(0, 0, prices, cache)
}

func createCache[T any](N int, val T) [][]T {
    ans := make([][]T, N)
    for i := range N {
        ans[i] = []T{val, val}
    }
    return ans
}

func run(idx int, taken int, prices []int, cache [][]int) int {
    N := len(prices)
    if idx == N && taken == 1 {
        return -INF
    }
    if idx == N && taken == 0 {
        return 0
    }
    if cache[idx][taken] != -1 {
        return cache[idx][taken]
    }
    if taken == 1 {
        cache[idx][taken] = max(
            prices[idx],
            run(idx + 1, taken, prices, cache),
        )
        return cache[idx][taken]
    }
    cache[idx][taken] = max(
        -prices[idx] + run(idx + 1, 1, prices, cache),
        run(idx + 1, 0, prices, cache),
    )
    return cache[idx][taken]
}