A dealer produces a sequence s1, …, sn of .cards, face up, where each card si has a value vi. Then two players take turns picking a card from the sequence, but can only pick the first or the last card of the (remaining) sequence. The goal is to collect cards of largest total value. (For example, you can think of the cards as bills of different denominations). Assume n is even.
The detailed algorithm is discussed in the Algorithm.pdf file.
The algorithm to solve the problem has been implemented in three ways:
- recursive
- top-down
- bottom-up (Dynamic Programming)
The time complexity of the dynamic programming solution is: O(N^2)
📦Card-Game-DP ┣ 📜main.cpp ┗ 📜README.md