DP problem with one of the states being related to the current diagonal line, from abc 311

Правка en1, от raghavmangla04, 2023-07-23 15:45:06

Here is the link to the problem: https://atcoder.jp/contests/abc311/tasks/abc311_f

Problem Statement basically states that there is a grid of characters of size n*m if grid[i][j]=='.' that means square(i,j) is white if grid[i][j]=='#' that means square(i,j) is black

necessary condition for grid to be beautiful is that if square (i,j) is black , square (i+1,j) and square(i+1,j+1) should also be black

we can repaint a white cell to a black cell, and were asked to find the number of beautiful grids possible

I wanted to ask about the dp solution of this problem using memoization instead of tabulation, like what exactly the transitions would be in memoized solution (Pls ignore grammatical errors)

Теги dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский raghavmangla04 2023-07-23 15:45:06 806 Initial revision (published)