Paths in a grid

Our next problem is to find a path from the upper-left corner to the lower-right corner of an $n \times n$ grid, such that we only move down and right. Each square contains a positive integer, and the path should be constructed so that the sum of the values along the path is as large as possible.

The following picture shows an optimal path in a grid:

The sum of the values on the path is 67, and this is the largest possible sum on a path from the upper-left corner to the lower-right corner.

Assume that the rows and columns of the grid are numbered from 1 to $n$, and $\texttt{value}[y][x]$ equals the value of square $(y,x)$. Let $\texttt{sum}(y,x)$ denote the maximum sum on a path from the upper-left corner to square $(y,x)$. Now $\texttt{sum}(n,n)$ tells us the maximum sum from the upper-left corner to the lower-right corner. For example, in the above grid, $\texttt{sum}(5,5)=67$.

We can recursively calculate the sums as follows: \[ \texttt{sum}(y,x) = \max(\texttt{sum}(y,x-1),\texttt{sum}(y-1,x))+\texttt{value}[y][x] \]

The recursive formula is based on the observation that a path that ends at square $(y,x)$ can come either from square $(y,x-1)$ or square $(y-1,x)$:

Thus, we select the direction that maximizes the sum. We assume that $\texttt{sum}(y,x)=0$ if $y=0$ or $x=0$ (because no such paths exist), so the recursive formula also works when $y=1$ or $x=1$.

Since the function \texttt{sum} has two parameters, the dynamic programming array also has two dimensions. For example, we can use an array

#![allow(unused)]
fn main() {
let mut sum: Vec<Vec<usize>>= vec![vec![]];
}

and calculate the sums as follows:

#![allow(unused)]
fn main() {
use std::cmp;
let value = vec![ vec![3, 7, 9, 2, 7],
                    vec![9, 8, 3, 5, 5],
                    vec![1, 7, 9, 8, 5],
                    vec![3, 8, 6, 4, 10],
                    vec![6, 3, 9, 7, 8],];
let mut sum = value.clone();
let n = value.len()-1;
for y in 1..=n{
    for x in 1..=n{
        sum[y][x] = cmp::max(sum[y][x-1], sum[y-1][x])+value[y][x];
print!("{} ", sum[y][x]);
    }
println!("");
}
}