I came about this problem looking for interesting DP problems. I tried with no luck to find which could be the overlapping sub-problems to explore and solve and tabulate. But it is my belief there are none and this problem can't be solved using DP.
Explanation of the problem rules can be seen here:
A turskish Roulette is a type of roulette which consists of:
- S amount of slots, each one with a number between -64 and 64.
- B amount of balls, each one with a number between -64 and 64 too.
- 3 <= S <= 250 & 1 <= B <= 1/S
- Each ball takes 2 slots of the roulette when they settle.
- For each ball, let L be the sum of the 2 slots value numbers times it's number.
- If the number L is negative the player loses that amount, else he wins that amount.
- The balls will always settle in the order they were introduced into the roulette, ej. If I throw the balls 1, 2 & 3 then the ball 2 will always be between 1 and 3.
- The objective is to find the max profit the owner of the roulette can have(max amount a player can lose in 1 turn) given a specific roulette with S number of slots and B number of balls each of them with their respective values.
I tried implementing a solution but the apparent lack of overlapping sub-problems made it impossible.
Things I already tried is the tabulation of the max_profit for a ball given a certain amount of slots. But I'm still short of the answer.
So, are there overlapping problems that can be helpful with memoization or tabulation?