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:

2461246134623461234613562356123562456124561345623456123456

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 }