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$
  • 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. Aug 13 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. Aug 13 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$ – VashTheStampede Aug 14 at 16:44
0
$\begingroup$

Well, the state should be dp[n] which is the optimal answer for some prefix of size n, and considering the different tiles, the transitions should be intuitive:

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

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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