Dynamic Programming- Calculating visit in a weighted matrix

Question

I found this question on a forum chat on and while looking at it I thought I can solve it using recursion,

A group of friends is split into cells in a room in a random arrangement of m X n cell locations in a rectangular or square form, such that each person in a cell can see all the people in their cell as well as the people in all the cells at the higher or equal position in row or column number. You are required to find out how many persons can be seen by each cell player from their respective cells i.e. you have to print the view matrix. persons in cell [i,j] can see all the players in cell [a,b], where a = i to m and b = j to n.

Let there is a matrix= \begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix} The output must be =\begin{bmatrix}9&6&3\\6&4&2\\3&2&1\end{bmatrix}

After hours of thinking about it, I realized that this question can be done using dynamic programming, I don't know enough about dynamic programming, after few tutorials from the internet, I am confused, Can anyone refer me a very exact question like this on the Internet,I am unable to find a question like this, I wish to learn about this topic by doing this question. Otherwise,you can also tell me how questions like this are done. I will keep editing as I understand how to do this question. Thanks.

Few resources that helped me that it is dynamic programming question:

What is dynamic programming about? When can I use dynamic programming to reduce the time complexity of my recursive algorithm?

Answer 1

A problem is called solvable by Dynamic Programming if its solution can be calculated by solving its sub-problems.

Let's see how the current state of the given problem depends on its previous states (aka sub-problems).

Let the answer to the block in colour C be denoted by Ans(C).

We can clearly see that,

Ans(PINK) = 1 + Ans(BLUE) + Ans(ORANGE) - Ans(GREEN)

Note: we are subtracting the GREEN block because it was added twice (once in ORANGE and once in BLUE).

Mathematically speaking, if Ans(i,j) = answer to the block starting from (i,j) and ending at (n,m).

Ans(i,j) = 1 + Ans(i+1,j) + Ans(i,j+1) - Ans(i+1,j+1) This is known as the Dynamic Programming transition.

The base cases are self-explanatory :)

2D Prefix Sums (generalised solution): https://usaco.guide/silver/more-prefix-sums?lang=cpp

Answer 2

Let $A[i,j]$ be the total number of people a person in that cell can see.

The following recurrence can help you:

$$A[i,j]= \begin{cases} m\times n, & \text{if $i=0$ and $j=0$}\\ A[i,j-1]-m, & \text{if $i=0$ and $j≠0$}\\ A[i-1,j]-n, & \text{if $i≠0$ and $j=0$}\\ A[i-1,j-1] -m-n+1, & \text{otherwise} \end{cases}$$

Try and work through the math for yourself. If you still have trouble understanding the logic, then feel free to ask.

More generally, to solve problems using dynamic programming, take care of the base case first. In this case, it's the first cell which is the only one that is sort of "hardcoded". Notice how the rest of the cells are all defined based on a previous cell in the table. If you're familiar with induction (which I really hope you are), then this is equivalent to relying on the induction hypothesis.

Hope that helped :)