###

This is easy backtracking problem which can be solved in O(n*d^2) complexity.

But this could also solved in 1025^2 using dp using range sum.

take input and make entries in dp[1025][1025];

Preproccess the 1025x1025 array using :

dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+dp[i][j];

then,
use recurrence relation to find max

dp[i+d][j+d]-dp[i+d][j-d-1]-dp[i-d-1][j+d]+dp[i-d-1][j-d-1]; for all (i,j) between d+1 to 1025-d

## No comments:

## Post a Comment