sumOfStones

Cho một ma trận m x n (m hàng và n cột). Mỗi ô trên ma trận có chứa một số lượng đá nhất định nằm trong khoảng từ 1 đến 100. Bạn phải thu thập nhiều đá nhất có thể theo quy tắc sau:

• Bắt đầu bằng một ô bất kì trên hàng đầu tiên và thu thập các viên đá trên ô đó. Sau đó di chuyển đến một ô ở hàng tiếp theo và thu thập đá trên ô đó, và cứ thế cho tới hàng cuối cùng.
• Khi di chuyển từ một ô sang ô ở hàng tiếp theo, bạn chỉ có thể di chuyển tới ô ngay bên dưới, hoặc theo đường chéo sang trái, phải.

Cho số lượng các viên đá trên ma trận, cho biết số lượng đá tối đa thu được.

Ví dụ:

Với đầu vào arr là ma trận   thì đầu ra sum_Of_Stones(arr) = 32

• Giải thích:
  • Ta có cách chọn như sau: 7+1+8+5+4+7

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

• [Đầu vào] matrix of integer: arr
  1 ≤ arr.size, arr[i].size, arr[i][j] ≤ 100
  

• [Đầu ra] Integer
  Tổng số đá thu thập được