Sudo Placement[1.5] | Wolfish

Given a N x N matrix where value at cell (i, j) is the cost of moving from a cell (i, j) to cell (i – 1, j – 1), (i – 1, j) or (i, j – 1). Your task is to find the maximum cost path from (N – 1, N – 1) cell to (0, 0) cell in the N x N matrix (0 – based indexing). However, you have some restrictions on the movement from one cell to the other cell. If you are at (i, j) cell and (i + j) is a power of 2, you can only move to (i – 1, j – 1) cell. If (i + j) is not a power of 2 then you can move to (i – 1, j) or (i, j – 1)

Examples: 

Input :[1 2 3 1
        4 5 6 1
        7 8 9 1
        1 1 1 1]
Output: 16 
The maximum cost path is: 
(3, 3) -> (3, 2) -> (2, 2) -> (1, 1) -> (0, 0).
Cost pathwise is: 
1 + 1 + 9 + 5 = 16.

Input: [1 2 
        3 4]
Output: 4 

Optimal Substructure: 

The problem is a variation of Min-Cost problem. The path to reach (0, 0) from (n-1, n-1) must be through the three cells (i, j-1) or (i-1, j) or (i-1, j-1). A top-down recursive function will be called, for every value of m and n, check if (m+n) is a power of 2 or not. If it is a power of 2, then move to cell(m-1, n-1) and add the value at a[m][n]. Hence the cost will be:  

cost = a[m][n] + maxCost(a, m – 1, n – 1)

If it is not a power of 2, then we can move to two of cells (m-1, n) and (m, n-1). So the cost will be: 

cost = a[m][n] + max(maxCost(a, m – 1, n), maxCost(a, m, n – 1))

Below is the recursive implementation of the above approach: 

16

Time Complexity: O(2^N)

Approach using Memoization

In the above recursion, many sub-problems are being repeatedly called. To reduce the number of repetitive calls, memoization has been used. The common point of observation is that only two parameters value are changing at every function call. So if we memoize the returned value in a dp[][] array, the number of calls will be reduced to N^2. Hence store the computed value of every maxCost(m, n) in dp[m][n]. If the maxCost(m, n) is called more than once, then the extra calls of the function will be reduced by returning the value stored at dp[m][n]. 

Below is the efficient implementation of the above approach: 

16

Complexity Analysis:

• Time Complexity: O(N²) 
• Auxiliary Space: O(N²)

Note: To implement a bottom-up approach, we need to check if ((m+1) + (n+1)) is a power of 2 or not instead of (m+n) as the moves are in top-down order.