Membiarkan Amenjadi moleh npersegi panjang bilangan bulat positif , di mana mdan njuga bilangan bulat positif .

Kami tertarik pada jalur RoD ('Kanan-atau-Bawah') dari sel kiri atas Ake sel kanan bawah; dalam jalur RoD, setiap sel yang berurutan dari jalur tersebut adalah satu sel di sebelah kanan atau satu sel di bawah dari sel sebelumnya.

Dengan adanya jalur RoD semacam itu, kita dapat mengambil jumlah sel di Adalam jalur itu.

Sebagai contoh, perhatikan matriks 4 oleh 3:

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

Maka kita dapat mempertimbangkan jalur RoD:

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

yang memiliki jumlah 1+2+1+2+1+1=8. Perlu dicatat bahwa jalur ini memiliki jumlah terkecil dari semua jalur RoD yang mungkin dari kiri atas ke kanan bawah dalam matriks itu.

Jadi, tantangan yang diusulkan adalah untuk menyediakan fungsi / program terpendek dalam bahasa pilihan Anda yang menghasilkan jumlah minimum jalur RoD dari kiri atas ke kanan bawah dalam matriks yang diberikan A.

Celah terlarang yang biasa berlaku. Masukan Anda dapat dalam format apa pun yang wajar; output Anda harus berupa bilangan bulat.

Ini adalah kode-golf; jawaban dinilai berdasarkan jumlah byte.

Uji Kasus

[ [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 byte

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

Cobalah online!

Bagaimana itu bekerja

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

Ilustrasi

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 byte

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)

Cobalah online!

Berkomentar

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 byte

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

Cobalah 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 byte

Terima kasih kepada @Giuseppe karena menunjukkan kesalahan, sekarang diperbaiki.

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

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

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 byte

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

Cobalah online!

Solusi naif: beralih melalui array (turun kolom), mengganti setiap entri dengan jumlah itu sendiri dan minimum tetangga di atas dan ke-kiri, jika ada, lalu kembalikan entri terakhir.

Perl 6 , 57 54 byte

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

Cobalah online!

Penjelasan

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 byte

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}

Cobalah online!

-9 byte berkat Sapi dukun

Python 3 , 108 byte

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)

Cobalah online!

Tidak disatukan

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)

Jelly , 21 byte

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

Cobalah online!

Bagaimana?

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 byte

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

Cobalah online!

+⍀+\ jumlah parsial secara horizontal dan vertikal - ini memberikan perkiraan awal yang terlalu tinggi untuk jalur ke setiap kotak

9e9(... )⍣≡terapkan "..." hingga konvergensi, pada setiap langkah melewati sejumlah sangat besar (9 × 10 ⁹ ) sebagai argumen kiri

,tambahkan 9e9-s di sebelah kiri dari perkiraan saat ini

2⊣/ ambil yang pertama dari setiap pasangan sel yang berurutan, secara efektif menjatuhkan kolom terakhir

2⊣⌿⍪hal yang sama secara vertikal - taruh 9e9di atas dan letakkan baris terakhir

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

⍵+ tambahkan matriks asli

⊢⌊ coba tingkatkan perkiraan saat ini dengan itu

⊃⌽, sel kanan bawah

Arang , 46 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan: Ini mungkin akan lebih pendek jika ada tiga argumen reducedi Charcoal.

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

Isi ulang array yang berfungsi dengan nilai besar kecuali yang pertama yang nol.

Ｆθ«

Loop di atas baris input.

≔§η⁰ζ

Inisialisasi total saat ini dengan elemen pertama dari array yang berfungsi.

ＦＬι«

Loop di atas kolom input.

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

Ambil minimum dari total saat ini dan elemen saat ini dari array yang berfungsi dan tambahkan elemen saat ini dari input untuk memberikan total arus yang baru.

§≔ηκζ

Dan simpan itu kembali dalam array yang berfungsi siap untuk baris berikutnya.

»»Ｉζ

Cetak total setelah input selesai diproses.

Jelly , 17 byte

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

Cobalah online!

Java 8, 197 193 byte

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 byte terima kasih @ceilingcat .

Cobalah online.

Penjelasan umum:

Saya sebenarnya sudah melakukan tantangan ini sekitar setahun yang lalu dengan Project Euler # 81 , kecuali itu terbatas pada matriks persegi daripadaN oleh Mmatriks. Jadi saya sedikit mengubah kode saya dari dulu ke akun untuk itu.

Saya pertama-tama menjumlahkan baris paling bawah dan kolom paling kanan dari sel paling belakang. Jadi mari kita gunakan contoh matriks tantangan:

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

Sel terakhir tetap sama. Sel terakhir kedua baris bawah menjadi jumlah yang: 1+1 = 2, dan sama untuk sel terakhir kedua kolom paling kanan: 1+7 = 8. Kami terus melakukan ini, jadi sekarang matriksnya terlihat seperti ini:

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

Setelah melakukan itu, kita melihat semua baris yang tersisa satu per satu dari bawah ke atas dan kanan ke kiri (kecuali untuk kolom / baris terakhir), dan kita mencari setiap sel di kedua sel di bawahnya dan di sebelah kanan untuk melihat mana yang lebih kecil.

Jadi sel yang mengandung angka itu 6menjadi 8, karena di 2bawahnya lebih kecil dari 8kanannya. Kemudian kita melihat yang 1berikutnya (ke kiri), dan melakukan hal yang sama. Itu 1menjadi 5, karena di 4bawahnya lebih kecil dari 8kanannya.

Jadi setelah kita selesai dengan baris kedua hingga terakhir, matriksnya terlihat seperti ini:

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

Dan kami terus melakukan ini untuk seluruh matriks:

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

Sekarang sel pertama akan berisi hasil kami, yaitu 8 dalam hal ini.

Penjelasan kode:

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 byte

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

Cobalah online!

-1 byte karena potongan tidak diperlukan - Anda tidak dapat mengambil kepala dari daftar kosong

Mungkin ada banyak ruang untuk bermain golf ini, tetapi saya perlu tidur.

Pendekatan bermuara pada mencoba setiap nilai untuk output, terkecil pertama, ( ∧≜.) sampai jalan dapat ditemukan ( b|bᵐ) ke sudut kanan bawah ( ~g~g) yang menghasilkan jumlah itu ( hhX&...↰+↙X).

Java (JDK) , 223 byte

Mengambil input sebagai Daftar 2D int.

Tambahan 19 byte untuk import java.util.*;disertakan.

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

Cobalah online!

Bagaimana itu bekerja

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 byte

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

Cobalah online!

Jika Bmerupakan transpose dari A, maka definisi masalah menyiratkan ituf(A)==f(B) .

A[1:]adalah array yang Ahilang baris atasnya. zip(*A[1:])adalah array yang Ahilang kolom paling kiri dan dipindahkan.sum(sum(A,()))adalah jumlah semua elemen dalam A.

Jika Ahanya memiliki satu kolom atau satu baris, hanya ada satu jalur, jadi fkembalikan jumlah semua elemen di A; kalau tidak kita recurse dan kembali penjumlahan dari A[0][0]+ yang lebih kecil dari fdari Ahilang baris atas dan fdari Ahilang kolom paling kiri.