# Recursion to dynamic programming [closed]

I was trying to solve a problem on de-arrangements (Number of partial derangement such that exactly prime number discs are found away from their natural positions? (Any number of non-prime K disks may also be found in or out of their natural positions)).

Somehow solved it using recursion but my code fails (taking long time to show output sometimes it gets freezes) on larger inputs for parameter move like (1000, 1000000), working fine for smaller inputs. Any approach to optimize this recursive function with Dynamic Programming with better time complexity.

static BigDecimal derangements(int move, int dontCare) {

if (move < 1)
return factorial(dontCare);

// recursion
move--;
BigDecimal result = derangements(move, dontCare).multiply(BigDecimal.valueOf(dontCare));
if (move > 0) {
result = (derangements(move - 1, dontCare + 1).multiply(BigDecimal.valueOf(move))).add(result);
}

return result;
}


I tried something like this but failed to correctly implement it. I know it's wrong. Any correct approach or implementation would do.

static BigDecimal derangements(int move, int dontCare) {
BigDecimal[] moveResult = new BigDecimal[move + 1];

moveResult[0] = factorial(dontCare);

for (int i = 1; i < move; i++) {
moveResult[i] = moveResult[i - 1].multiply(BigDecimal.valueOf(dontCare));
}

while ( move  > 1) {
int i = 1;
moveResult[i] = moveResult[i - 1].multiply(BigDecimal.valueOf(dontCare))