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 _ _

JavaScript (ES6), 78 77 76 bytes

m=>(M=g=s=>(v=(m[y]||0)[x])?g(s+=v,y++)|g(s,x++,y--)*x--|M<s?M:M=s:0)(x=y=0)

Try it online!

Commented

m => (                      // m = input matrix

  M =                       // initialize the minimum M to a non-numeric value

  g = s =>                  // g = recursive function taking the current sum s

    (v = (m[y] || 0)[x]) ?  //   if the current cell v is defined:

      g(s += v, y++) |      //     do a recursive call at (x, y + 1)

      g(s, x++, y--) * x--  //     do a recursive call at (x + 1, y)

      |                     //     if at least one call did not return 0 (which means

                            //     that we haven't reached the bottom-right corner)

      M < s ?               //     or M is less than s (false if M is still non-numeric):

        M                   //       return M unchanged

      :                     //     else:

        M = s               //       update M to s, and return this new value

    :                       //   else (we're outside the bounds of the matrix):

      0                     //     return 0

)(x = y = 0)                // initial call to g with s = x = y = 0

Haskell, 63 57 bytes

f x@((a:_:_):c:d)=a+min(f$c:d)(f$tail<$>x)

f x=sum$id=<<x

Try it online!

f x@((a:_:_):c:d)=           -- if it's at least a 2x2 matrix

   a+min                     -- add the top left element to the minimum of the

                             -- path costs of

        f$c:d                --   the matrix with the first row dropped and

        f$tail<$>x           --   the matrix with the first column dropped

f x=                         -- else, i.e. a 1xm or nx1 matrix, i.e. a vector

    sum$id=<<x               -- return the sum of this vector

MATL, 38 36 30 29 bytes

Thanks to @Giuseppe for pointing out a mistake, now corrected.

lyZyqsG&nghZ^Yc!tsGz=Z)Ys)sX<

Try it online! Or verify all test cases.

Explanation

l        % Push 1

y        % Input, implicit. Duplicate from below. Pushes the input below

         % the current 1, and a copy of the input on top

Zy       % Size of input. Gives [m, n]

qs       % Subtract 1 element-wise, sum. Gives m+n-2

G        % Push input again

&n       % Push size as two separate numbers. Gives m, n

gh       % Transform n into 1 and concatenate horizontally. Gives [m, 1]

Z^       % Cartesian power of [m, 1] raised to m+n-2. This produces the

         % Cartesian tuples as row of a matrix. A typical tuple may be

         % [1, m, 1, m, m]. This will define a path along the matrix in

         % linear, column-wise indexing (down, then across). So 1 means

         % move 1 step down, and m means move m steps "down", which is

         % actually 1 step to the right

Yc       % Concatenate strcat-like. This prepends the 1 that is at the

         % bottom of the stack to each row

!        % Transpose. Each tuple (extended with initial 1) is now a column

!ts      % Duplicate, sum of each column

Gz       % Number of nonzeros of input. Gives m*n-1

=Z)      % Keep only columns that sum m*n. That means that, starting from

Ys       % Cumulative sum of each column. This defines the path

)        % Index: pick entries specified by the path

s        % Sum of each column

X<       % Minimum

         % Display, implicit

R, 90 bytes

function(m){l=sum(m|1)

if(l>1)for(i in 2:l)m[i]=m[i]+min(m[i-1],m[max(0,i-nrow(m))])

m[l]}

Try it online!

The naive solution: iterate through the array (down the columns), replacing each entry by the sum of itself and the minimum of its above and to-the-left neighbors, if they exist, then return the last entry.

Perl 6, 57 54 bytes

my&f={|.flat&&.[0;0]+min (f(.[1..*]),f $_>>[1..*])||0}

Try it online!

Explanation

my&f={                                               }  # Function f

      |.flat&&  # Return empty slip if matrix is empty

              .[0;0]+  # Value at (0,0) plus

                     min  # Minimum of

                          f(.[1..*])   # Rows 1..*

                                     f $_>>[1..*]  # Columns 1..*

                         (          ,            )||0  # Or 0 if empty

Röda, 100 89 bytes

f A{g={|x,y|{g(x-1,y)if[x>0];g(x,y-1)if[y>0];[0]if[x+y=0]}|min|[A[x][y]+_]}g#A-1,#A[0]-1}

Try it online!

-9 bytes thanks to Cows quack

Python 3, 108 bytes

def f(A,m,n,i=0,j=0):r=i+1<m and f(A,m,n,i+1,j);d=j+1<n and f(A,m,n,i,j+1);return A[i][j]+min(r or d,d or r)

Try it online!

Ungolfed

def f(A, m, n, i=0, j=0):

    right = i + 1 < m and f(A, m, n, i + 1, j)

    down  = j + 1 < n and f(A, m, n, i, j + 1)

    return A[i][j] + min(right or down, down or right)

APL (Dyalog Classic), 37 32 bytes

{⊃⌽,9e9(⊢⌊⍵+(2⊣⌿⍪)⌊2⊣/,)⍣≡+⍀+⍵}

Try it online!

+⍀+ partial sums horizontally and vertically - this provides an initial overestimate for the paths to each square

9e9(...)⍣≡ apply "..." until convergence, at each step passing some very large number (9×10⁹) as left argument

, add 9e9-s to the left of the current estimate

2⊣/ take the first from each pair of consecutive cells, effectively dropping the last column

2⊣⌿⍪ same thing vertically - put 9e9 on top and drop last row

(2⊣⌿⍪) ⌊ 2⊣/, minima

⍵+ add the original matrix

⊢⌊ try to improve the current estimates with that

⊃⌽, bottom-right cell

Charcoal, 46 bytes

≔Ｅ§θ⁰∧κΣ§θ⁰ηＦθ«≔§η⁰ζＦＬι«≔⁺⌊⟦§ηκζ⟧§ικζ§≔ηκζ»»Ｉζ

Try it online! Link is to verbose version of code. Explanation: This would probably be shorter if there was a three-argument reduce in Charcoal.

≔Ｅ§θ⁰∧κΣ§θ⁰η

Prefill the working array with large values except for the first which is zero.

Ｆθ«

Loop over the rows of the input.

≔§η⁰ζ

Initialise the current total with the first element of the working array.

ＦＬι«

Loop over the columns of the input.

≔⁺⌊⟦§ηκζ⟧§ικζ

Take the minimum of the current total and the current element of the working array and add the current element of the input to give the new current total.

§≔ηκζ

And store that back in the working array ready for the next row.

»»Ｉζ

Print the total once the input has been completely processed.

Jelly, 21 bytes

ZI_.ỊȦ

ŒJŒPÇƇLÐṀœị⁸§Ṃ

Try it online!

How?

ZI_.ỊȦ - Link 1: isDownRight?: List of 2d indices (limited to having no repetitions)

Z      - transpose

 I     - deltas (vectorises)

  _.   - subtract 1/2 (vectorises)

    Ị  - insignificant? (effectively _.Ị here is like "v in {0,1}? 1 : 0")

     Ȧ - any & all (0 if a 0 is present when flattened, else 1)



ŒJŒPÇƇLÐṀœị⁸§Ṃ - Main Link: list of lists of integers, A

ŒJ             - multi-dimensional indices of A

  ŒP           - power-set

     Ƈ         - filter keep only those truthy by:

    Ç          -   last link as a monad

       ÐṀ      - filter keep only those maximal by:

      L        -   length

           ⁸   - chain's left argument, A

         œị    - multi-dimensional index into (vectorises)

            §  - sum each

             Ṃ - minimum

Jelly, 17 bytes

XL,1ẋLḊŒ!1;ⱮÄịẎ§Ṃ

Try it online!

Java (JDK), 223 bytes

Takes input as a 2D List of ints.

Additional 19 bytes for import java.util.*; included.

import java.util.*;m->{var l=m.get(0);int s=m.size(),c=l.size(),x=-1>>>1,a=l.get(0);return s*c<2?a:Math.min(s>1?n.n(new Vector(m.subList(1,s))):x,c>1?n.n(new Vector<>(m){{replaceAll(l->new Vector(l.subList(1,c)));}}):x)+a;}

Try it online!

How it works

import java.util.*;                                     // Import needed for Vector class

m->{                                                    // Lambda that takes a 2D list of integers

    var r=m.get(0);                                     // Store first row in variable

    int h=m.size(),                                     // Store number of rows

        w=r.size(),                                     // Store number of columns

        x=-1>>>1,                                       // Store int max

        a=r.get(0);                                     // Store the current cell value

    return h*w<2?a:                                     // If matrix is single cell return value

        Math.min(                                       // Otherwise return the minimum of...



            h>1?                                        // If height is more than 1

                n.n(                                    // Recursively call this function with 

                    new Vector(m.subList(1,h))):        // a new matrix, without the top row

                x,                                      // Otherwise use int max as there is no row below this



            w>1?                                        // If width is more than 1

                n.n(new Vector<>(m){{                   // Recursively call this function with a new matrix             

                    replaceAll(                         // where all columns have been replaced with 

                        l->new Vector(l.subList(1,w))   // cloned lists without the leftmost column

                    );

                }}):                                    // Otherwise use int max as there is

                x                                       // no column to the right of this

        )+a;                                            // Add the current cell value to the result before returning

}

Python 2, 86 bytes

f=lambda A:len(A)>1<len(A[0])and A[0][0]+min(f(zip(*A)[1:]),f(A[1:]))or sum(sum(A,()))

Try it online!

If B is the transpose of A, then the problem definition implies that f(A)==f(B).

A[1:] is the array A missing its top row. zip(*A[1:]) is the array A missing its leftmost column and transposed. sum(sum(A,())) is the sum of all elements in A.

If A has only a single column or single row, there is only one path, so f returns the sum of all elements in A; otherwise we recurse and return the sum of A[0][0] + the smaller of f of A missing the top row and f of A missing the leftmost column.

Java 8, 197 bytes

m->{int r=m.length-1,c=m[0].length-1,i=r,j=c,a,b;for(;i-->0;m[i][c]+=m[i+1][c]);for(;j-->0;m[r][j]+=m[r][j+1]);for(i=r;i-->0;)for(j=c;j-->0;b=m[i][j+1],m[i][j]+=a<b?a:b)a=m[i+1][j];return m[0][0];}

Try it online.

General explanation:

I actually already did this challenge about a year ago with Project Euler #81, except that was limited to a square-matrix instead of an N by M matrix. So I slightly modified my code from back then to account for that.

I first sum the bottom row and rightmost column from the very last cell backwards. So let's use the example matrix of the challenge:

1, 2, 3, 4

5, 1, 6, 7

8, 2, 1, 1

The last cell remains the same. The second last cell of the bottom row becomes the sum: 1+1 = 2, and the same for the second last cell of the rightmost column: 1+7 = 8. We continue doing this, so now the matrix looks like this:

 1,  2,  3, 12

 5,  1,  6,  8

12,  4,  2,  1

After doing that, we look at all the remaining rows one by one from bottom to top and right to left (except for the last column/row), and we look for each cell at both the cell below it and right of it to see which one is smaller.

So the cell containing the number 6 becomes 8, because the 2 below it is smaller than the 8 right of it. Then we look at the 1 next of it (to the left), and do the same. That 1 becomes 5, because the 4 below it is smaller than the 8 right of it.

So after we're done with the second to last row, the matrix looks like this:

 1,  2,  3, 12

10,  5,  8,  8

12,  4,  2,  1

And we continue doing this for the entire matrix:

 8,  7, 11, 12

10,  5,  8,  8

12,  4,  2,  1

Now the very first cell will contain our result, which is 8 in this case.

Code explanation:

m->{                    // Method with integer-matrix input and integer return-type

  int r=m.length-1,     //  Amount of rows minus 1

      c=m[0].length-1,  //  Amount of columns minus 1

      i=r,j=c,          //  Index integers

      a,b;              //  Temp integers

  for(;i-->0;m[i][c]+=m[i+1][c]);

                        //  Calculate the suffix-sums for the rightmost column

  for(;j-->0;m[r][j]+=m[r][j+1]);

                        //  Calculate the suffix-sums for the bottom row

  for(i=r;i-->0;)       //  Loop over the rows backwards

    for(j=c;j-->0       //   Inner loop over the columns backwards

        ;               //     After every iteration:

         b=m[i][j+1],   //      Set `b` to the value left of the current cell

         m[i][j]+=a<b?  //      If `a` is smaller than `b`:

                   a    //       Add `a` to the current cell

                  :     //      Else:

                   b)   //       Add `b` to the current cell

      a=m[i+1][j];      //    Set `a` to the value below the current cell

  return m[0][0];}      //  Return the value in the cell at index {0,0} as result