Vamos a Aser una mpor nmatriz rectangular de positivos enteros, donde my nson también positivos enteros.

Estamos interesados ​​en rutas RoD ('Derecha o Abajo') desde la celda superior izquierda a la celda Ainferior derecha; en una ruta RoD, cada celda sucesiva de la ruta es una celda a la derecha o una celda abajo de la celda anterior.

Dada cualquier ruta de RoD, podemos tomar la suma de las celdas Aen esa ruta.

Por ejemplo, considere la matriz 4 por 3:

[ [1, 2, 3, 4],
  [5, 1, 6, 7],
  [8, 2, 1, 1] ]

Entonces podemos considerar la ruta de RoD:

1 > 2   3   4
    v
5   1   6   7
    v
8   2 > 1 > 1

que tiene una suma de 1+2+1+2+1+1=8. Vale la pena señalar que esta ruta tiene la suma más pequeña de todas las rutas de RoD posibles desde la parte superior izquierda a la inferior derecha en esa matriz.

Por lo tanto, el desafío propuesto es proporcionar la función / programa más corto en su idioma de elección que genere la suma mínima que puede tener una ruta RoD desde la parte superior izquierda a la inferior derecha en una matriz determinada A.

Las lagunas prohibidas habituales están vigentes. Su entrada puede estar en cualquier formato razonable; Su salida debe ser un número entero.

Este es el código de golf; Las respuestas se puntúan por número de bytes.

Casos de prueba

[ [5] ] -> 5

[ [5, 2] ] -> 7

[ [5], 
  [2] ] -> 7

[ [ 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#.$){.!._]

Pruébalo en línea!

Cómo funciona

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

Ilustración

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)

Pruébalo en línea!

Comentado

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

Pruébalo en línea!

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

Gracias a @Giuseppe por señalar un error, ahora corregido.

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

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

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]}

Pruébalo en línea!

La solución ingenua: iterar a través de la matriz (hacia abajo en las columnas), reemplazando cada entrada por la suma de sí misma y el mínimo de sus vecinos superiores e izquierdos, si existen, luego devuelva la última entrada.

Perl 6 , 57 54 bytes

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

Pruébalo en línea!

Explicación

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}

Pruébalo en línea!

-9 bytes gracias a 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)

Pruébalo en línea!

Sin golf

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)

Jalea , 21 bytes

ZI_.ỊȦ
ŒJŒPÇƇLÐṀœị⁸§Ṃ

Pruébalo en línea!

¿Cómo?

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

APL (Dyalog Classic) , 37 32 bytes

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

Pruébalo en línea!

+⍀+\ sumas parciales horizontal y verticalmente: esto proporciona una sobreestimación inicial de los caminos a cada cuadrado

9e9(... )⍣≡aplique "..." hasta la convergencia, en cada paso pasando un número muy grande (9 × 10 ⁹ ) como argumento izquierdo

,agrega 9e9-s a la izquierda de la estimación actual

2⊣/ tome la primera de cada par de celdas consecutivas, dejando caer efectivamente la última columna

2⊣⌿⍪ lo mismo verticalmente - poner 9e9 encima y suelte la última fila

(2⊣⌿⍪) ⌊ 2⊣/, mínimos

⍵+ agregue la matriz original

⊢⌊ tratar de mejorar las estimaciones actuales con eso

⊃⌽, celda inferior derecha

Carbón , 46 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación: Esto probablemente sería más corto si hubiera tres argumentos reduceen Charcoal.

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

Rellene el conjunto de trabajo con valores grandes, excepto el primero, que es cero.

Ｆθ«

Pase sobre las filas de la entrada.

≔§η⁰ζ

Inicialice el total actual con el primer elemento de la matriz de trabajo.

ＦＬι«

Pase sobre las columnas de la entrada.

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

Tome el mínimo del total actual y el elemento actual de la matriz de trabajo y agregue el elemento actual de la entrada para obtener el nuevo total actual.

§≔ηκζ

Y guárdelo en la matriz de trabajo listo para la siguiente fila.

»»Ｉζ

Imprima el total una vez que la entrada se haya procesado por completo.

Jalea , 17 bytes

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

Pruébalo en línea!

Java 8, 197193 bytes

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

-4 bytes gracias a @ceilingcat .

Pruébalo en línea.

Explicación general:

De hecho, ya hice este desafío hace aproximadamente un año con el Proyecto Euler # 81 , excepto que estaba limitado a una matriz cuadrada en lugar de una matriz Npor M. Entonces modifiqué un poco mi código desde entonces para dar cuenta de eso.

Primero sumo la fila inferior y la columna de la derecha desde la última celda hacia atrás. Entonces usemos la matriz de ejemplo del desafío:

1, 2, 3, 4
5, 1, 6, 7
8, 2, 1, 1

La última celda permanece igual. La segunda última celda de la fila inferior se convierte en la suma: 1+1 = 2y lo mismo para el segundo última celda de la columna más a la derecha: 1+7 = 8. Continuamos haciendo esto, así que ahora la matriz se ve así:

 1,  2,  3, 12
 5,  1,  6,  8
12,  4,  2,  1

Después de hacer eso, observamos todas las filas restantes, una por una, de abajo hacia arriba y de derecha a izquierda (excepto la última columna / fila), y buscamos cada celda tanto en la celda debajo como a la derecha para ver cuál es más pequeño

Por lo tanto, la celda que contiene el número se 6vuelve 8, porque el 2siguiente es más pequeño que el 8derecho. Luego miramos el 1siguiente (a la izquierda) y hacemos lo mismo. Eso se 1convierte 5, porque el 4siguiente es más pequeño que el 8derecho.

Entonces, después de terminar con la penúltima fila, la matriz se ve así:

 1,  2,  3, 12
10,  5,  8,  8
12,  4,  2,  1

Y continuamos haciendo esto para toda la matriz:

 8,  7, 11, 12
10,  5,  8,  8
12,  4,  2,  1

Ahora la primera celda contendrá nuestro resultado, que es 8en este caso.

Explicación del código:

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,              //  Index integer
      a;                //  Temp integer
  for(;i-->0;m[i][c]+=m[i+1][c]);
                        //  Calculate the suffix-sums for the rightmost column
  for(i=c;i-->0;m[r][i]+=m[r][i+1]);
                        //  Calculate the suffix-sums for the bottom row
  for(i=r*c;i-->0       //  Loop over the rows and columns backwards
      ;                 //     After every iteration:
       r=m[i/c][i%c+1], //      Set `r` to the value left of the current cell
       m[i/c][i%c]+=a<r?//      If `a` is smaller than `r`:
                 a      //       Add `a` to the current cell
                :       //      Else:
                 r)     //       Add `r` to the current cell
      a=m[i/c+1][i%c];  //    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

Brachylog , 26 25 bytes

∧≜.&{~g~g|hhX&{b|bᵐ}↰+↙X}

Pruébalo en línea!

-1 byte porque el corte no es necesario: no puede tomar el encabezado de una lista vacía

Probablemente haya mucho espacio para jugar al golf, pero necesito dormir.

El enfoque se reduce a probar cada valor para la salida, el más pequeño primero, ( ∧≜.) hasta que se pueda encontrar una ruta ( b|bᵐ) a la esquina inferior derecha ( ~g~g) que produce esa suma ( hhX&...↰+↙X).

Java (JDK) , 223 bytes

Toma entrada como una lista 2D de entradas.

19 bytes adicionales para import java.util.*;incluidos.

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;}

Pruébalo en línea!

Cómo funciona

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,()))

Pruébalo en línea!

Si Bes la transposición de A, entonces la definición del problema implica quef(A)==f(B) .

A[1:]es la matriz que Afalta su fila superior. zip(*A[1:])es la matriz que Afalta su columna más a la izquierda y se transpone. sum(sum(A,()))es la suma de todos los elementos enA .

Si Asolo tiene una columna o una fila, solo hay una ruta, por lo que fdevuelve la suma de todos los elementos A; de lo contrario, son recursivos y devolver la suma de A[0][0]+ la más pequeña de fde Afalta la fila superior y fde la Afalta de la columna de la izquierda.