# Dynamic Programming- Calculating visit in a weighted matrix

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:

– D.W.
Aug 29, 2022 at 16:14

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

• +1, I think this has a really good visual representation of the solution. I would've maybe thought it more intuitive to use i-1 and j-1 instead of i+1 and j+1, but that could be just me. n-dimensional prefix sums in general can be expressed as [sum of all items 1 less in 1 dimension]-[sum of all items 1 less in 2 dimensions]+[sum of all items 1 less in 3 dimensions]-..., sort of like finding the area of a venn diagram with n different overlapping circles. Dec 28, 2022 at 22:31

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

$$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}$$