Problem Links
Difficulty
Easy DP
PREREQUISITES
Ad hoc
Problem
Given a grid of 2 × 1 tiles. We have to find the maximum sum of the absolute difference of the number in two consecutive tiles , such as that arrangement covers the entire grid.
EXPLANATION
The problem can be easily be solved using DP.
The tiles are 2X1 rectangular ones. Now let the grid be a[2][N] , where N is the length of matrix.
let dp[i] denote the maximum sum of the arrangement till length i.
Therefore
dp[i+1]=max(dp[i]+abs(a[0][i+1]-abs[1][i+1]), dp[i-2]+abs(a[0][i]-a[0][i+1])+abs(a[1][i])-a[1][i]))
We can either add a single vertical brick to the grid of length i or we can add two horizontal bricks to the grid. We just have to see which one gives the maximum answer
Editorialist’s Solution