Probability of maximum points on a random path in a matrix

Given a ‘N*N’ 2d matrix consisting of positive integers, the task is to find the probability of collecting maximum points by moving either up(from {i,j} to {i+1,j}) or right (from {i,j} to {i,j+1}) starting from cell (0, 0) randomly till we reach the cell (N-1, N-1). Whenever we land on a cell, our total points is updated by summing it with the number in that cell.

Examples :

Input : arr[][] = {{1, 1, 1},
                   {1, 1, 1},
                   {1, 1, 1}}
Output : 1
Explanation :
All the possible paths will result in a total of 5 points.
Since, all the paths will yield in maximum, probability will be 1.

Input : arr[][] = {{1, 1, 2},
                   {1, 1, 2},
                   {1, 1, 2}}
Output : 0.25
Explanation :
There is only one possible path for maximum points.
{(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)}
Probability of going to (0, 1) = 0.5
Probability of going to (0, 2) given we are at (0, 1) = 0.5
Probability of going to (1, 2) given we are at (0, 2) = 1
Probability of going to (2, 2) given we are at (1, 2) = 1
Thus, the final answer equals 0.5 * 0.5  * 1 * 1 = 0.25

Let dp1[i][j] be the maximum points that we can get if we get to the cell {i, j} from {0 ,0} by going only up or right. Let dp2[i][j] be the probability of getting to the cell {i, j} with total points of dp1[i][j] from {0 ,0}, given we move up or right randomly. Algorithm: For each cell (i, j), we will first evaluate for cells (i,j-1) and (i-1, j). Case 1:(If dp1[i][j-1] = dp1[i-1][j])

If both are same, a path will exist from both the cells to the cell {i, j} 
that will yield maximum points. In this case, both the paths are to be
considered in the required probability(dp2[i][j]).

dp1[i][j] can be updated as dp1[i][j] = dp1[i][j-1] + arr[i][j]

dp2[i][j] can be updated as follows:
Sub-case 1 (i != n-1 && j != n-1) - dp2[i][j] = 0.5*dp2[i-1][j] + 0.5*dp2[i][j-1]
Sub-case 2 (i == n-1 && j != n-1) - dp2[i][j] = 0.5*dp2[i-1][j] + dp2[i][j-1]
Sub-case 3 (i != n-1 && j == n-1) - dp2[i][j] = dp2[i-1][j] + 0.5*dp2[i][j-1]

Case 2:(dp1[i][j-1] > dp1[i-1][j])

A path will exist from cell (i, j-1). Probability
is to be calculated for path from cell with larger points.

dp1[i][j] can be updated as dp1[i][j] = dp1[i][j-1] + arr[i][j]

dp2[i][j] can be updated as follows:
Sub-case 1 (i == n-1) - dp2[i][j] = dp2[i][j-1]
Sub-case 1 (i != n-1) - dp2[i][j] = 0.5 * dp2[i][j-1]

Case 3:(dp1[i][j-1] < dp1[i-1][j])

dp1[i][j] can be updated as dp1[i][j] = dp1[i-1][j] + arr[i][j]

dp2[i][j] can be updated as follows:
Sub-case 1 (j == n-1) - dp2[i][j] = dp2[i-1][j]
Sub-case 1 (j != n-1) - dp2[i][j] = 0.5 * dp2[i-1][j]

Note :

There maybe multiple possible ways that scores the maximum points.

#include <iostream>
#define n 4

using namespace std;

//2d matrices to store
//the states of dp
int dp1[n][n];
double dp2[n][n];
bool v[n][n];


//function to find the probability
//using memoisation
pair<int, double> findProbability(int arr[][n],
                                        int i, int j)
{
    
    //bases cases
    if(i==0 && j==0)
        return {arr[0][0],1.0};
    
    if(i < 0 || j < 0)
        return {-1, -1};
    if(v[i][j])
        return {dp1[i][j], dp2[i][j]};
        
        
        
    v[i][j] = 1;
    
    
    pair<int, double> a, b;
    a = findProbability(arr, i - 1, j);
    b = findProbability(arr, i, j - 1);
    
    
    //if both of the paths
    //result in maximum
    if(a.first == b.first)
    {
        dp1[i][j] = arr[i][j] + a.first;
        if(i != n-1)
            dp2[i][j] = 0.5 * b.second;
        else 
            dp2[i][j] = b.second;
        if(j != n-1)
            dp2[i][j] += 0.5 * a.second;
        else 
            dp2[i][j] += a.second;
    }
    //if only one of the paths result in maximum
    else
    {
        if(a.first > b.first)
        {
            dp1[i][j] = arr[i][j] + a.first;
            if(j != n-1)
                dp2[i][j] = 0.5 * a.second;
            else 
                dp2[i][j] = a.second;    
        }
        else
        {
            dp1[i][j] = arr[i][j] + b.first;
            if(i != n-1)
                dp2[i][j] = 0.5 * b.second;
            else 
                dp2[i][j] = b.second;    
        }
    }
    return {dp1[i][j], dp2[i][j]};
    
    
}   



int main()
{
    
  //input matrix
  int arr[n][n] = {{1, 1, 1, 2},
                   {1, 2, 1, 2},
                   {1, 2, 2, 2},
                   {1, 1, 1, 2}};
  
  //calling the required function
  cout << findProbability(arr, n-1, n-1).second;

  return 0;
}

Time Complexity : O(n²)