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 解法：
package fib;
import java.util.ArrayList;
public class climbingstairs {
public ArrayList<String> climb (int n) {
if (n <= 0) return null;
ArrayList<String> res = new ArrayList<String>();
if (n == 1) {
res.add("1");
return res;
}
if (n == 2) {
res.add("2");
res.add("12");
return res;
}
ArrayList<String> former2 = climb(n-2);
for (String item : former2) {
res.add(item+Integer.toString(n));
}
ArrayList<String> former1 = climb(n-1);
for (String item : former1) {
res.add(item+Integer.toString(n));
}
return res;
}
public static void main(String[] args) {
climbingstairs obj = new climbingstairs();
ArrayList<String> res = obj.climb(6);
for (String item : res) {
System.out.println(item);
}
}
}
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>>
import java.util.ArrayList;
public class climbingstairs {
public ArrayList<String> climb (int n) {
if (n <= 0) return null;
ArrayList<ArrayList<String>> results = new ArrayList<ArrayList<String>>();
for (int i=1; i<=n; i++) {
results.add(new ArrayList<String>());
}
if (n >= 1) {
results.get(0).add("1");
}
if (n >= 2) {
results.get(1).add("2");
results.get(1).add("12");
}
for (int i=3; i<=n; i++) {
ArrayList<String> step = results.get(i-1);
ArrayList<String> former2 = results.get(i-3);
for (String item : former2) {
step.add(item+Integer.toString(i));
}
ArrayList<String> former1 = results.get(i-2);
for (String item : former1) {
step.add(item+Integer.toString(i));
}
}
return results.get(n-1);
}
public static void main(String[] args) {
climbingstairs obj = new climbingstairs();
ArrayList<String> res = obj.climb(5);
for (String item : res) {
System.out.println(item);
}
}
}