Note that after each cut the remaining piece of pizza always has the lower right coordinate at (rows-1,cols-1).

Use dynamic programming approach with states (row1, col1, c) which computes the number of ways of cutting the pizza using "c" cuts where the current piece of pizza has upper left coordinate at (row1,col1) and lower right coordinate at (rows-1,cols-1).

For the transitions try all vertical and horizontal cuts such that the piece of pizza you have to give a person must contain at least one apple. The base case is when c=k-1.

Additionally use a 2D dynamic programming to respond in O(1) if a piece of pizza contains at least one apple.