递推
# 递推
- 上楼梯 小明上楼梯可以一次上一阶、两阶、三阶。求小明上n阶楼梯有多少种走法。 f(n) = f(n-1) + f(n-2) + f(n-3) 递归的方式
private int countStair(int n) {
if (n == 1){ return 1; }
if (n == 2){ return 2; }
if (n == 3){ return 4; }
return countStair(n-1) + countStair(n-2) + countStair(n-3);
}
1
2
3
4
5
6
2
3
4
5
6
循环
private int countStair2(int n){
if (n == 1){ return 1; }
if (n == 2){ return 2; }
if (n == 3){ return 4; }
int x = 1,y = 2,z=4;
int sum = 0;
int i = 4;
while(i<=n){
sum = x+y+z;
x = y;
y=z;
z=sum;
i++;
}
return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
递归调用会开辟栈空间，而且对于多分支可能存在重复的计算。
- 机器人走方格 一个x*y的网格，一个机器人智能走格点且智能向右或向下走，要从左上角走到右下角，问有多少种走法。 f(x,y) = f(x-1,y)+f(x,y-1)
递归比较简单，下面给出循环解法
@Test
public void t_机器人走方格() {
int x= 4,y=4;
int a[][] = new int[y][x];
for (int i = 0; i < x; i++) {
a[0][i] = 1;
}
for (int i = 0; i < y; i++) {
a[i][0] = 1;
}
for (int i = 1; i < y; i++) {
for (int j = 1; j < x; j++) {
a[i][j] = a[i-1][j] + a[i][j-1];
}
}
System.out.println(a[y-1][x-1]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 子集
增量构造法 二进制法
# 全排列
集合法 遍历元素，将元素加入左中右组成新串 需要开辟新空间 交换法 将剩余元素与子串头部交换，依次确定头部元素，需要回溯恢复字符串数组。 原址，但是没法保证生成的顺序 前缀法 依次将可用元素追加到子串尾部 可保证生成顺序
# 封闭形式直接解
汉诺塔 f(n) = 2f(n-1)-1 = 2^n-1
编辑 (opens new window)
上次更新: 2023/04/09, 16:34:32