DP - Sample Problems

1. Given a set of positive integers, partition the set into two such that the difference between the sum of the two sets is minimized.

   Solution:

   Let the S={x₁, x₂, …, x_n} be the set. Then the problem is equivalent to asking "choose some subset of S such that the sum of all elements in S plus the negative of all the elements not in S is as close to zero as possible.". We can solve this using a naive recursive call as follows:

   f(i, trytomake) = whichever is closer to trytomake of {f(i+1, trytomake−x_i)+x_i, f(i+1, trytomake+x_i)−x_i}

   This can be memoized by using a hashtable. Memoization using an array is unwise because trytomake could be very large but sparse.

2. You and a friend are playing a game using an n-sided dice labeled from 1 to n. You first throw the dice and record the number showing up. Then your friend throws the dice. If his toss is larger than yours, than your friend wins. If his toss is the same, then he toss again. Otherwise, it is your turn to toss the dice. You win if your toss is larger than your friend's toss. Otherwise, you keep tossing if it's the same, and lose your turn if it's smaller. The game continues until one of you win. Given n, return the probability that you win.

   solution by Sam