Recursion memorization table
Don't Repeat Yourself
Your main() function starts with 3 loops to initialize your table array. There are several problems here. First, it writes past the end of the array. If your array has n + 1 elements, then you can only write to 0 through n. Element n + 1 is out-of-bounds. So each of your loops is writing to one element of the next row, and then one extra row at the end, and one element past that, too. The loops should only go from 0 to n. This happens to work because you later read past the end of the array, too. If you're going to do that, you need to allocate n + 2 rows and columns.
Next, you're writing several elements 3 times. You can combine these 3 loops into 1 and do far less initialization. Further, you should use braces around all loop and conditional bodies because there's the potential to create errors in the future if you don't.
Also, you've switched i and j in the last loop which is highly confusing and could easily be missed by a reader.
Here's how I would write your initialization code:
table = new double [ n + 2 ][ n + 2 ]
for (int i = 0; i &lt; n + 1; i++)
{
    for (int j = 0; j &lt; k; j++)
    {
        if (i + j &lt; k)
        {
            table [ i ][ j ] = 0.0;
        }
        else
        {
            table [ i ][ j ] = -1.0;
        }
    }

    for (int j = k; j &lt; n + 1; j++)
    {
        table [ i ][ j ] = 1.0;
    }
}

Now no element should be touched more than once, no elements past the end of the array should be written to, and no array indexes are flipped.
You're also calculating (double)d / (double)s twice. You should calculate it once and re-use this value.
Naming
You should choose better names for your variables. i and j are fine for loop indexes as they are commonly used that way and nobody will be confused by them. However, I'd rename n, s, and k. I'd name n something descriptive like numThrows; k should be something like numNeeded, and s should be numSides.
Likewise, s, r, and d are not very helpful names for the arguments to game().
Speed
I haven't profiled your code, which is the real way to find out which parts are slow. I have seen many cases where casting variables from one type to another causes significant slowdowns. Since the bulk of your game() function is either calling itself or casting values, I recommend just making the arguments to the function be double to begin with. Of course, you can't use a double as an index into an array. So you could either pass the r and d values as both doubles and ints.