CODEWITHSUNDEEP
javarecursiondynamic-programming
Waqar
Waqar

Reputation: 263

Find Path with maximum value where T squares value can be doubled

Given a square matrix of size N*N, where each cell is associated with a specific cost. A path is defined as a specific sequence of cells which starts from top left cell move only right or down and ends on bottom right cell. We want to find the path with maximum value. Now to make things even more interesting: you also have T tokens. You can use the tokens to double the value on the current square. You can only use one token on any given square.

This is how I have solved the first part of the problem.

public static long pathWithMaxCost(int[][] n, int tokens) {
    int[][] arr = new int[n.length][n[0].length];

    // starting position
    arr[arr.length - 1][0] = n[arr.length - 1][0];

    // first column
    for (int i = arr.length - 2; i >= 0; i--) {
        arr[i][0] = arr[i + 1][0] + n[i][0];
    }

    // last row
    for (int i = 1; i < arr[0].length; i++) {
        arr[arr.length - 1][i] = arr[arr.length - 1][i - 1] + n[arr.length - 1][i];
    }

    for (int i = arr.length - 2; i >= 0; i--) {
        for (int j = 1; j < arr[0].length; j++) {
            arr[i][j] = Math.max(arr[i][j - 1], arr[i + 1][j]) + n[i][j];

        }
    }

    return arr[0][arr[0].length - 1];
}

Now how can I handle the token part, T square values can be doubled?

Upvotes: 2

Views: 74

Answers (3)

Izaz Ul Hassan
Izaz Ul Hassan

Reputation: 36

static long pathWithMaxCostHash(int[][] n, int x, int y, int tokkens) {
    if (x < 0 || x >= n.length || y < 0 || y >= n[0].length)
        return -1;
    String key = x + ":" + y + ":" + tokkens;

    if (map.containsKey(key))
        return map.get(key);

    if(x==n.length-1&&y==0) {
        if (tokkens > 0 && n[x][y] > 0) {
            map.put(key,(long)n[n.length-1][0]*2);
            return 2*n[n.length-1][0];

        }
        map.put(key,(long)n[n.length-1][0]);
        return n[n.length-1][0];

    }

    //without picking double
    long val = n[x][y]
            + Math.max(pathWithMaxCostHash(n, x + 1, y, tokkens), pathWithMaxCostHash(n, x, y - 1, tokkens));
    //with picking double
    if (tokkens > 0 && n[x][y] > 0) {
        long val2 = 2 * n[x][y] + Math.max(pathWithMaxCostHash(n, x + 1, y, tokkens - 1),
                pathWithMaxCostHash(n, x, y - 1, tokkens - 1));
        val2 = Math.max(val, val2);
        map.put(key, val2);
        return val2;
    }

    map.put(key, val);
    return val;

}

Upvotes: 2

גלעד ברקן
גלעד ברקן

Reputation: 23955

Add another dimension for T, so the general check for a cell would be:

m[y][x][t] = max(
  2 * n[y][x] + m[y-1][x][t-1],
  2 * n[y][x] + m[y][x-1][t-1],
  n[y][x] + m[y-1][x][t],
  n[y][x] + m[y][x-1][t]
)
for all y,x,t

Let's consider the edge cases:

// first element
if x + y == 0:
  m[y][x][0] = n[y][x]
  m[y][x][1] = 2 * n[y][x]
  m[y][x][t] = -Infinity, for t > 1

// first row
if y == 0:
  m[y][x][t] = max(
    2 * n[y][x] + m[y][x-1][t-1],
    n[y][x] + m[y][x-1][t]
  )

// first column
if x == 0:
  m[y][x][t] = max(
    2 * n[y][x] + m[y-1][x][t-1],
    n[y][x] + m[y-1][x][t]
  )

Upvotes: 1

Rakesh
Rakesh

Reputation: 466

I'll give you a recursive approach, guess you can figure out dynamic programming based solution with this. Initialize your dp 2d array with 0's

function: pathWithMaxCost(int x,int y,int tokens, int arr[][],int dp[][])
    if(dp[x][y]) return dp[x][y];
    few boundary conditions here...
    return dp[x][y]=max(arr[x][y]+pathWithMaxCost(x,y+1,tokens,arr), arr[x][y]+pathWithMaxCost(x+1,y,tokens,arr), (arr[x][y]*2)+pathWithMaxCost(x,y+1,tokens-1,arr), (arr[x][y]*2)+pathWithMaxCost(x+1,y,tokens-1,arr))

Upvotes: 1

Related Questions