你的位置:首页 > Java教程

[Java教程]Climbing Stairs


stair climbing, print out all of possible solutions of the methods to climb a stars, you are allowed climb one or two steps for each time; what is time/space complexity? (use recursion)

这道题难是难在这个ArrayList<String> res是用在argument还是返回值,纠结了好久

Recursion 解法:

 1 package fib; 2  3 import java.util.ArrayList; 4  5 public class climbingstairs { 6    7   public ArrayList<String> climb (int n) { 8     if (n <= 0) return null; 9     ArrayList<String> res = new ArrayList<String>();10     if (n == 1) {11       res.add("1");12       return res;13     }14     if (n == 2) {15       res.add("2");16       res.add("12");17       return res;18     }19     ArrayList<String> former2 = climb(n-2); 20     for (String item : former2) {21       res.add(item+Integer.toString(n));22     }23     ArrayList<String> former1 = climb(n-1);24     for (String item : former1) {25       res.add(item+Integer.toString(n));26     }27     return res;28   }29 30   31   public static void main(String[] args) {32     climbingstairs obj = new climbingstairs();33     ArrayList<String> res = obj.climb(6);34     for (String item : res) {35       System.out.println(item);36     }37   }38 39 }

Sample input : 6

Sample Output: 

246
1246
1346
2346
12346
1356
2356
12356
2456
12456
13456
23456
123456

 

 follow up: could you change the algorithm to save space? 

这就想到DP,用ArrayList<ArrayList<String>>

 1 import java.util.ArrayList; 2  3 public class climbingstairs { 4    5   public ArrayList<String> climb (int n) { 6     if (n <= 0) return null; 7     ArrayList<ArrayList<String>> results = new ArrayList<ArrayList<String>>(); 8     for (int i=1; i<=n; i++) { 9       results.add(new ArrayList<String>());10     }11     if (n >= 1) {12       results.get(0).add("1");13     }14     if (n >= 2) {15       results.get(1).add("2");16       results.get(1).add("12");17     }18 19     for (int i=3; i<=n; i++) {20       ArrayList<String> step = results.get(i-1);21       ArrayList<String> former2 = results.get(i-3);22       for (String item : former2) {23         step.add(item+Integer.toString(i));24       }25       ArrayList<String> former1 = results.get(i-2);26       for (String item : former1) {27         step.add(item+Integer.toString(i));28       }29     }30     return results.get(n-1);31   }32 33   34   public static void main(String[] args) {35     climbingstairs obj = new climbingstairs();36     ArrayList<String> res = obj.climb(5);37     for (String item : res) {38       System.out.println(item);39     }40   }41 42 }