1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Please don't delete your question after you've received an answer. Thank you! $\endgroup$
    – D.W.
    Aug 29, 2022 at 16:14

2 Answers 2

1
$\begingroup$

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).

enter image description here

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

$\endgroup$
1
  • 1
    $\begingroup$ +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. $\endgroup$
    – LogicalX
    Dec 28, 2022 at 22:31
0
$\begingroup$

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 :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.