Let A be an m by n rectangular matrix of positive integers, where m and n are also positive integers.

We are interested in RoD ('Right-or-Down') paths from the upper-left cell of A to the lower right cell; in an RoD path, each successive cell of the path is either one cell to the Right of or one cell Down from the previous cell.

Given any such RoD path, we can take the sum of the cells in A in that path.

For example, consider the 4 by 3 matrix:

[ [1, 2, 3, 4],

  [5, 1, 6, 7],

  [8, 2, 1, 1] ]

Then we can consider the RoD path:

1 > 2   3   4

    v

5   1   6   7

    v

8   2 > 1 > 1

which has a sum of 1+2+1+2+1+1=8. It's worth noting that this path has the smallest sum of all possible RoD paths from upper left to lower right in that matrix.

So, the proposed challenge is to provide the shortest function/program in your language of choice that outputs the minimum sum an RoD path from upper left to lower right can have in a given matrix A.

The usual forbidden loopholes are in effect. Your input can be in any reasonable format; your output must be an integer.

This is code-golf; answers are scored by number of bytes.

Test Cases

[ [ 9 , 1 , 12, 3 ],

  [ 12, 11, 6 , 11],

  [ 12, 9 , 2 , 11] ] -> 40



[ [ 6 , 8 , 11, 2 ],

  [ 3 , 6 , 7 , 6 ],

  [ 6 , 2 , 8 , 12] ] -> 37



[ [ 4 , 5 , 8 , 4 ],

  [ 6 , 5 , 9 , 4 ],

  [ 2 , 5 , 6 , 8 ] ] -> 31



[ [ 4 , 5 , 15, 18, 30],

  [ 26, 26, 3 , 4 , 5 ],

  [ 7 , 9 , 29, 25, 14],

  [ 16, 1 , 27, 13, 27],

  [ 23, 11, 25, 24, 12],

  [ 17, 23, 7 , 14, 5 ] ] -> 94



[ [ 10, 15, 7 , 2 , 9 ],

  [ 24, 5 , 2 , 1 , 25],

  [ 2 , 12, 14, 30, 18],

  [ 28, 4 , 12, 22, 14],

  [ 15, 21, 21, 11, 4 ],

  [ 21, 15, 21, 29, 9 ] ] -> 103

J, 42 bytes

v(+}.<.}:)&.>/@{.[:</.(2#v=._1+1#.$){.!._]

Try it online!

How it works

v(+}.<.}:)&.>/@{.[:</.(2#v=._1+1#.$){.!._]

                         v=._1+1#.$         Sum of two dimensions - 1; assign to v

                                            (v is a verb)

                      (2#          ){.!._]  Extend the given array in both dimensions

                 [:</.  Extract the antidiagonals as boxed arrays

v             @{.  Take the first `v` antidiagonals

 (       )&.>/     Reduce over unboxed items:

   }.<.}:            Given the right item R, take the minimum of R[1:] and R[:-1]

  +                  Add to the left item

Illustration

1 2 3 4  Input array, dimensions = 3,4

5 1 6 7

8 2 1 1



1 2 3 4 _ _  Extended to 6,6 with filler _ (infinity)

5 1 6 7 _ _

8 2 1 1 _ _

_ _ _ _ _ _

_ _ _ _ _ _

_ _ _ _ _ _



1            Diagonalize and take first 6 rows

5 2

8 1 3

_ 2 6 4

_ _ 1 7 _

_ _ _ 1 _ _



Reduction: left+min(right[1:], right[:-1])

1                                          1  => 8

5 2                               5  2  => 10 7

8 1 3                   8 1 3  => 12 5 11

_ 2 6 4      _ 2 6 4 => _ 4 8 12

_ _ 1 7 _ => _ _ 2 8 _

_ _ _ 1 _ _