RectPath

发表于 由



  1. import java.math.BigInteger;   

  2. import java.util.HashMap;   

  3. import java.util.Map;   

  4.   

  5. public class RectPath {   

  6.   

  7.     private static int endX = 0;   

  8.     private static int endY = 0;   

  9.     private static Map<String, BigInteger> cache = null;   

  10.   

  11.     public static void main(String[] args) {   

  12.   

  13.         int width = 311;   

  14.         int height = 311;   

  15.         cache = new HashMap<String, BigInteger>();   

  16.   

  17.         BigInteger paths = getPath(width, height);   

  18.   

  19.         System.out.println("(0,0)-(" + width + ", " + height + ")=" + paths);   

  20.     }   

  21.   

  22.     public static BigInteger getPath(int x, int y) {   

  23.   

  24.         endX = Math.abs(x);   

  25.         endY = Math.abs(y);   

  26.   

  27.         return getRectPath(0, 0);   

  28.     }   

  29.   

  30.     private static BigInteger getRectPath(int startX, int startY) {   

  31.   

  32.         if(startX == endX || startY == endY) {   

  33.                

  34.             return new BigInteger("1");   

  35.         } else {   

  36.             if(cache.containsKey(startX + "," + startY)) {   

  37.                 return cache.get(startX + "," + startY);   

  38.             } else {   

  39.                 BigInteger result = getRectPath(startX + 1, startY).add(getRectPath(startX, startY + 1));   

  40.                 cache.put(startX + "," + startY, result);   

  41.                 return result;   

  42.             }   

  43.         }   

  44.     }   

  45.   

  46. }   

  1. da shang
    donate-alipay
               donate-weixin weixinpay

发表评论↓↓