Finding the maximum sum in a path from (0, 0) to (N-1, M-1) when can only move to right or down

Complexity

  • Time:
  • Space:

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

    const N = DP.length;
const M = DP[0].length;

function update(i, j, value) {
  DP[i][j] = value;
  
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (i === 0 && j === 0) {
      update(i, j, D[i][j]);
    } else if (i === 0) {
      
      update(i, j, DP[i][j - 1] + D[i][j]);
      
    } else if (j === 0) {
      
      update(i, j, DP[i - 1][j] + D[i][j]);
      
    } else {
      
      update(i, j, Math.max(DP[i][j - 1], DP[i - 1][j]) + D[i][j]);
      
    }
  }
}

console.log(`max = ${DP[N - 1][M - 1]}`);