第一题：三十九个台阶问题
package LanQiao.day03;
public class 三十九台阶 {
public static int stairCase(int count,int n){
if(count<0) return 0 ;
//这个地方结束的判断不只是等于0
//结束条件、
if(count==0){
if(n%2==0) return 1;
}
return stairCase(count-2,n+1)+
stairCase(count-1,n+1);
}
public static void main(String[] args) {
System.out.println(stairCase(39, 0));
}
}
第二题：栈的出入顺序
心得：当时做这个题的时候第一反应是直接写一个栈，后来才发现根本不用写出来
package LanQiao.day03;
import java.util.Stack;
public class 汽车入栈顺序 {
public static int sum=0;
public static int carQuestion(int carNumber, Stack stack){
//结束条件
if(carNumber==0){ return 1;} //只有一种条件
if(stack.size()==0){
stack.push(carNumber);
return carQuestion(carNumber-1,stack);
}else {
stack.push(carNumber);
sum+=carQuestion(carNumber-1,stack);
stack.pop();
Integer pop = stack.pop();
stack.push(carNumber);
sum+=carQuestion(carNumber-1,stack);
stack.pop();
stack.push(pop);
}
return sum;
}
public static int sum2=0;
public static int f(int n, int m) {
if (n == 0) {
return 1;
}
if (m == 0) {
return f(n - 1, 1);
}
return f(n - 1, m + 1)+
f(n, m - 1);
}
public static void main(String[] args) {
Stack integers = new Stack<>();
System.out.println(carQuestion(3, integers));
System.out.println(f(3, 0));
}
}
3：振兴中华问题
对于这种路径的题来说一般除了递归以外也会有动态规划的DP的方式
package LanQiao.day03;
public class 振兴中华 {
public static String[][] square={
{"从","我","做","起","振"},
{"我","做","起","振","兴"},
{"做","起","振","兴","中"},
{"起","振","兴","中","华"}
};
public static int findWayNumber(int x,int y){
if(x==square.length-1||y==square[0].length-1) return 1;
findWayNumber(x,y+1);
findWayNumber(x+1,y);
return findWayNumber(x,y+1)+findWayNumber(x+1,y);
}
public static int findWayNumberDp(){
//首先初始化最开始的两种情况
int[][] dp = new int[square.length][square[0].length];
//初始化最开始的点
dp[0][0]=0;
for (int i = 0; i < square.length; i++) {
dp[i][0]=1;
}
for (int i = 0; i
4：算式填充
package LanQiao.day03;
public class 算式填充 {
public static void main(String[] args) {
int []a={1,2,3,4,5,6,7,8,9};
find(a,8,"",110);
}
public static void find(int []a,int k,String so,int Goal){
//首先是递归结束的时候
if(k==0) {
if(a[0]==Goal) System.out.println(a[0]+so);
return;
}
//增加号
find(a,k-1,"+"+a[k]+so,Goal-a[k]);
//减号
find(a,k-1,"-"+a[k]+so,Goal+a[k]);
//不加符号
int old=a[k-1];
a[k-1]=Integer.parseInt(""+a[k-1]+a[k]);//相当于字符串拼接
find(a,k-1,so,Goal);//通过拼接的这个符号进去继续递归
a[k-1]=old;//回溯
}
}
5：公园找零问题
package LanQiao.day03;
import java.awt.*;
import java.util.Scanner;
public class 找零钱 {
public static int cash(int five,int one){
if(five 
