I'm struck how to find DP recurrence for:
You are given a binary square matrix M of size nxn. We define a (p,q, l)-triangle of M, where p >= 1, q >= 1, L >= 1, p+L >= n+1, and q+L >= n+1, as the set of elements M[i, j] satisfying p =< i < p+L, q =< j < q+L, and i+ j < p+q+L. Design an algorithm to find the largest (p,q, l)-triangle of M (“largest” means l is maximized) such that all its elements are “1”
EDIT: I added the original problem as requested:
I think I need to check first if:
element equal 1,
if so, check the element to its left, element in its top and element diagonally if equals "1"
if so increment the result,
but not sure how to put this into recurrence.