问题:
在此问题中,我们正在评估的场景如下:您正站在楼梯的底部,正走向顶部。小步幅将向上移动一个台阶,大步幅将向上移动两个台阶。您想根据大步和小步的不同组合来计算爬上整个楼梯的方法数量。例如,可以用三种不同的方式爬上三个台阶的楼梯:三个小步幅,一个小步幅然后一个大步幅,或者一个大步幅然后一个小步幅。
对WaysToClimb(3)的调用应产生以下输出:
1 1 1,
1 2,
2 1
我的代码:
public static void waysToClimb(int n){
if(n == 0)
System.out.print("");
else if(n == 1)
System.out.print("1");
else {
System.out.print("1 ");
waysToClimb(n - 1);
System.out.print(",");
System.out.print("2 ");
waysToClimb(n - 2);
}
}
我的输出:
1 1 1,
2,
2 1
我的递归似乎不记得如何解决它的想法了?
编辑:
谢谢你们的答复。抱歉,回复晚了
我知道了
public static void waysToClimb(int n){
String s ="[";
int p=0;
com(s,p,n);
}
public static void com(String s,int p,int n){
if(n==0 && p==2)
System.out.print(s.substring(0,s.length()-2)+"]");
else if(n==0 && p !=0)
System.out.print(s+"");
else if(n==0 && p==0)
System.out.print("");
else if(n==1)
System.out.print(s+"1]");
else {
com(s+"1, ",1,n-1);
System.out.println();
com(s+"2, ",2,n-2);
}
}
如果您明确地要打印所有路径(不同于计算路径或查找特定路径,则需要将它们一直存储到0。
public static void waysToClimb(int n, List<Integer> path)
{
if (n == 0)
{
// print whole path
for (Integer i: path)
{
System.out.print(i + " ");
}
System.out.println();
}
else if (n == 1)
{
List<Integer> newPath = new ArrayList<Integer>(path);
newPath.add(1);
waysToClimb(n-1, newPath);
}
else if (n > 1)
{
List<Integer> newPath1 = new ArrayList<Integer>(path);
newPath1.add(1);
waysToClimb(n-1, newPath1);
List<Integer> newPath2 = new ArrayList<Integer>(path);
newPath2.add(2);
waysToClimb(n-2, newPath2);
}
}
首次通话:waysToClimb(5, new ArrayList<Integer>());
下面提到的解决方案将与“深度优先搜索”类似,它将探索一条路径。路径完成后,它将回溯并探索其他路径:
public class Demo {
private static LinkedList<Integer> ll = new LinkedList<Integer>(){{ add(1);add(2);}};
public static void main(String args[]) {
waysToClimb(4, "");
}
public static void waysToClimb(int n, String res) {
if (ll.peek() > n)
System.out.println(res);
else {
for (Integer elem : ll) {
if(n-elem >= 0)
waysToClimb(n - elem, res + String.valueOf(elem) + " ");
}
}
}
}
public class Test2 {
public int climbStairs(int n) {
// List of lists to store all the combinations
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// initially, sending in an empty list that will store the first combination
csHelper(n, new ArrayList<Integer>(), ans);
// a helper method to print list of lists
print2dList(ans);
return ans.size();
}
private void csHelper(int n, List<Integer> l, List<List<Integer>> ans) {
// if there are no more stairs to climb, add the current combination to ans list
if(n == 0) {
ans.add(new ArrayList<Integer>(l));
}
// a necessary check that prevent user at (n-1)th stair to climb using 2 stairs
if(n < 0) {
return;
}
int currStep = 0;
// i varies from 1 to 2 as we have 2 choices i.e. to either climb using 1 or 2 steps
for(int i = 1; i <= 2; i++) {
// climbing using step 1 when i = 1 and using 2 when i = 2
currStep += 1;
// adding current step to the arraylist(check parameter of this method)
l.add(currStep);
// make a recursive call with less number of stairs left to climb
csHelper(n - currStep, l, ans);
l.remove(l.size() - 1);
}
}
private void print2dList(List<List<Integer>> ans) {
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans.get(i).size(); j++) {
System.out.print(ans.get(i).get(j) + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
Test2 t = new Test2();
t.climbStairs(3);
}
}
[请注意,此解决方案对于较大的输入将超时,因为这不是建议的递归解决方案,并且可能引发MLE(因为找到组合后我会创建一个新列表)。
希望这会有所帮助。