SRM 318 Div 2. Hard

class SimplifiedDarts():
    dp = [[-1]*3005 for _ in range(1005)]

    def tryToWin(self, w, n, p1, p2):

        p1 /= 100.0
        p2 /= 100.0
        return 100*self.calc(n, 0, w,  p1, p2)

    def calc(self, i, j, w, p1, p2):
        if self.dp[i][j] != -1:
            return self.dp[i][j]
        if i == 0:
            if j >= w:
                self.dp[i][j] = 1
            else:
                self.dp[i][j] = 0
        elif j > w:
            self.dp[i][j] = 1

        else:
            self.dp[i][j] = max(self.calc(i-1, j+3, w, p1, p2)*p2+self.calc(i-1, j, w, p1,p2) * (1-p2), self.calc(i-1, j+2, w, p1, p2)*p1 + self.calc(i-1, j, w, p1, p2) * (1-p1))

        return self.dp[i][j]