麻煩與歐拉計劃＃15

Question

這裏的問題：https://projecteuler.net/problem=15

我拿出我本以爲這對這項工作的模式，我已經看了別人做了什麼，他們已經做了相同的東西，如這裏：http://code.jasonbhill.com/python/project-euler-problem-15/但我總是得到不同的答案。這是我的代碼。

import java.util.*; 
public class Problem15 { 
    public static void main(String[] args) { 
     ArrayList<Long> list = new ArrayList<Long>(); 
     list.add((long)1); 
     int size; 
     for (int x = 1;x<20;x++){ 
      size = list.size(); 
      for(int y = 1;y<size;y++){ 
        long sum = list.get(y-1)+list.get(y); 
        list.set(y, sum); 
      } 
     list.add(list.get(size-1)*2); 
     System.out.println(list); 
     } 
    } 
} 

編輯： 在回答愛德華，我覺得我的方法是目前你在你的編輯之前說這是不是蠻力，但我只是從每個點求和的可能途徑格。但是，我不需要一個2D數組來做到這一點，因爲我只是從側面看可能的移動。這是我想要解釋我的過程的東西。

因此對於1x1。就像你說的，一旦你達到了一個方向的極限，你只能在另一個方向上行進，所以有兩種方法。這對於1x1來說並不是特別有用，但對於大一點的用戶來說並不是特別有用對於2x2，您知道右上角的右上角只有一條可能的路徑。同樣的邏輯適用於底角。而且，因爲你有一個你已經解決的方塊，一個1x1，你知道中間點有2條路徑。現在，如果你看到兩側，你會發現例如在它下面有2個點，右側有1個點的點具有這些相鄰點中路徑數量的總和，因此那個點必須有3個路徑。對於另一面，給出左上角3和3或2的總和3.

現在，如果你看看我的代碼，那就是它想要做的。索引爲0的元素始終爲1，對於數組的其餘部分，它將前一項和它自身相加，並替換當前項。最後，要找到路徑的總數，它只是最後一個數字的兩倍。因此，如果程序試圖解決4x4的問題，那麼陣列目前看起來像{1,4,10,20}。因此，程序會將它改爲{1,5,10,20}，然後{1，5，15，20}，然後{1,5,15,35}，最後，將路徑的總數{ 1，5，15，35，70}。我認爲這是你在回答中向我解釋的，但我的答案總是出錯。

Answer 1

認識到它比蠻力搜索更關心數學複雜性。

您有一個二維點數組，您可以選擇只在x或y方向遠離原點。因此，您可以像這樣代表您的旅行：

(0, 0), (1, 0), (1, 1), (2, 1), (2, 2) 

有些事情變得非常明顯。第一個是通過混亂的任何路徑將需要x + y步驟，穿過x + y + 1個位置。這是曼哈頓距離風格路徑的一個特徵。

第二個是，在任何一點上，直到你達到最大x或y，你可以選擇兩個選項（x或y）中的任何一個;但是，只要其中一個處於極限，剩下的唯一選擇就是反覆選擇非最大值，直到它變爲最大值。

有了這個，你可能有足夠的提示來解決數學問題。那麼你甚至不需要搜索不同的路徑來獲得可以解決問題的算法。

---編輯，得到多一點的提示的---

的路徑中的每個二維陣列可以被分解成較小的路徑二維陣列。因此，解決方案f(3, 5)其中函數f產生的路徑數等於f(2, 5) + f(3, 4)。需要注意的是f(0, 5)直接等於1一樣，f(3, 0)，因爲你不再有「選擇」時的路徑被迫是線性的。

一旦建模功能，你甚至不需要數組行走路徑....

f(1, 1) = f(0, 1) + f(1, 0) 
f(0, 1) = 1 
f(1, 0) = 1 
f(1, 1) = 1 + 1 
f(1, 1) = 2 

和一組3×3 verticies（喜歡舉的例子有）

f(2, 2) = f(1, 2) + f(2, 1) 
f(1, 2) = f(0, 1) + f(1, 1) 

（來自之前）

f(1, 1) = 2 
f(0, 2) = 1 
f(1, 2) = 2 + 1 = 3 

同樣（因爲它的鏡像）

f(2, 1) = 1 + 2 = 3 

所以

f(2, 2) = 3 + 3 = 6 

---最後的編輯（我希望！）---

好了，現在你可能會得到的想法，你真的兩個選擇（下井）或（右轉）。考慮一個包含4個「命令」，2個「下去」和2個「去吧」的包。您可以從包裏選擇多少種不同的方式？

這樣的「選擇」是置換，但由於我們選擇所有這些，它被稱爲「訂單」或「訂單」一種特殊類型的置換。

的二項式（一個或另一個）排序的數量由數學公式排除

數排序的= (A + B)!/(A! * B!)

其中A是A類型的物品的「計數」，和B是「計數」 類型的項目B

3x3的頂點，2點倒的選擇，2點正確的選擇

數量排序的= （2 + 2）！/ 2！* 2！

4!/1*2*1*2 
1*2*3*4/1*2*1*2 
(1*2)*3*4/(1*2)*1*2 
3*4/2 
12/2 
6 

你也許可以用手工做一個20 * 20，如果你需要的，但階乘式是很簡單的通過電腦做（儘管留意你不破壞與一個整數溢出的答案）。

Answer 2

另一種實現：

public static void main(String[] args) { 
    int n = 20; 
    long matrix[][] = new long[n][n]; 
    for (int i = 0; i < n; i++) { 
     matrix[i][0] = i + 2; 
     matrix[0][i] = i + 2; 
    } 
    for (int i = 1; i < n; i++) { 
     for (int j = i; j < n; j++) {  // j>=i 
      matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1]; 
      matrix[j][i] = matrix[i][j]; // avoids double computation (difference) 
     } 
    } 
    System.out.println(matrix[n - 1][n - 1]); 
} 

時間：43微秒（不打印）

它是基於以下矩陣：

| 1 2 3 4 ... 
--------------------- 
1 | 2 3 4 5 ... 
2 | 3 6 10 15 
3 | 4 10 20 35 
4 | 5 15 35 70 
. | . 
. | . 
. | . 

其中

6 = 3 + 3 
10 = 6 + 4 
15 = 10 + 5 
... 
70 = 35 + 35 

請注意，我用i + 2代替i + 1中實現，因爲第一個指數是0。

---

當然，最快的解決方案是使用一個數學公式（見Edwin的交）和它的代碼：

public static void main(String[] args) { 
    int n = 20; 
    long result = 1; 
    for (int i = 1 ; i <= n ; i++) { 
     result *= (i+n); 
     result /= i; 
    } 
    System.out.println(result); 
} 

僅需5微秒（不打印）。

如果您擔心精度損失，請注意連續數字n的乘積可以被n!整除。

爲了更好地理解爲什麼公式是：

 (d+r)! 
F = --------- , where |D| = d and |R| = r 
     d!*r! 

，而不是F = (d+r)!，假設每一個 「下」 和 「右」 有一個指標：

down1,right1,right2,down2,down3,right3 

第二個公式計算了上述「命令」的所有可能的排列，但在我們的例子中，down1，down2和down3之間沒有區別。所以，第二個公式將計算6（3!）次同樣的事情：

down1,down2,down3 
down1,down3,down2 
down2,down1,down3 
down2,down3,down1 
down3,down1,down2 
down3,down2,down1 

這就是爲什麼我們通過d!劃分(d+r)!。模擬爲r!。