0
$\begingroup$

I came across the following question while practising for my final algorithms exam, but I am unsure how to get a linear time complexity for this problem. I assumed it would require checking which tiling patterns are compatible with each other, but get a bit stuck on how to proceed.

Thanks!

Tiling Patterns

$\endgroup$
3
  • 2
    $\begingroup$ Please credit the source of all copied material. Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX) $\endgroup$
    – D.W.
    Commented Aug 13, 2020 at 3:32
  • 2
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. We have advice on how to approach dynamic programming problems: cs.stackexchange.com/tags/dynamic-programming/info. I suggest following the systematic approach outlined there, then edit your question to show what progress you've made and at what step of that process you get stuck. $\endgroup$
    – D.W.
    Commented Aug 13, 2020 at 3:33
  • $\begingroup$ When designing a DP algorithm I find useful to start with a naive recursive solution. Can you find a recursive solution that solves the problem in O(2ⁿ)? Once you have the recursion it's easy to apply memorization to it and then convert it to a "bottom up" DP algorithm :) $\endgroup$ Commented Aug 14, 2020 at 16:44

1 Answer 1

1
$\begingroup$

Well, the state should be dp[n], the optimal answer for some prefix of size n. Considering the different tiles, the transitions should be intuitive:

dp[n] = max(dp[n-2] + max(a[n], a[n-1]), dp[n-3] + max(a[n-1], a[n-2] + a[n]))

Of course, if any of the indices n-2, n-1, or n-3 are less than 0, then the involving terms should be omitted from the calculation. This is just a general representation of what the transition should be.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.