Project Euler - 015

dorodaloo

Problem 15:

• Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
• 
  How many such routes are there through a 20×20 grid?
  

• 从一个2×2网格的左上角开始，有6条（不允许往回走）通往右下角的路。
• 对于20×20的网格，这样的路有多少条？
  

dorodaloo

1. package main
   
2. 
   
3. func main() {
   
4.         p015(2)     // 6
   
5.         p015(20)    // 137846528820
   
6. }
   
7. 
   
8. func p015(n int) {
   
9.         a := make([]int64, n+1)
   
10.         for i := range a { a[i] = 1 }
    
11.         for i := 1; i < len(a); i++ {
    
12.                 a[i] *= 2
    
13.                 for j := i + 1; j < len(a); j++ {
    
14.                         a[j] += a[j-1]
    
15.                 }
    
16.         }
    
17.         println(a[len(a)-1])
    
18. }
    

复制代码