LeetCode-70-爬楼梯
70. 爬楼梯
难度简单
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
- Climbing Stairs
Easy
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
- 类似斐波那契数列的递归
F(N)=F(N-1)+F(N-2)
到达第N台阶，可以通过N-1的台阶跨一步，或者N-2的台阶一次性跨两步两种方式完成，所以是斐波那契数列方式
F(N)=F(N-1)+F(N-2) f(2)=2 f(1)=1
int[][] base = { { 1, 1 }, { 1, 0 } };
res = base^(N-2)
F(N)=`2*res[0][0]+ 1*res[1][0]`
时间复杂度可以做到O(longN)
class Solution {
public static int climbStairs(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return n;
}
int[][] base = { { 1, 1 }, { 1, 0 } };
int[][] res = matrixPower(base, n - 2);
return 2 * res[0][0] + res[1][0];
}
public static int[][] matrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];
for (int i = 0; i < res.length; i++) {
res[i][i] = 1;
}
// res = 矩阵中的1
int[][] tmp = m;// 矩阵1次方
for (; p != 0; p >>= 1) {
if ((p & 1) != 0) {
res = muliMatrix(res, tmp);
}
tmp = muliMatrix(tmp, tmp);
}
return res;
}
// 两个矩阵乘完之后的结果返回
public static int[][] muliMatrix(int[][] m1, int[][] m2) {
int[][] res = new int[m1.length][m2[0].length];
for (int i = 0; i < m1.length; i++) {
for (int j = 0; j < m2[0].length; j++) {
for (int k = 0; k < m2.length; k++) {
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;
}
}
斐波那契数列-矩阵求法
矩阵乘法+空间换时间(减少乘法，取模运算)
数列的递推公式为：f(1)=1，f(2)=2，f(n)=f(n-1)+f(n-2)(n>=3)
用矩阵表示为：
进一步，可以得出直接推导公式：
由于矩阵乘法满足结合律，在程序中可以事先给定矩阵的64，32，16，8，4，2，1次方，加快程序的执行时间。（有些题目需要取模运算，也可以事先进行一下）。给定的矩阵次幂，与二进制有关是因为，如下的公式存在解，满足Xi={0或1}：
为了保证解满足 Xi={0或1}，对上述公式的求解从右向左，即求解顺序为Xn，Xn-1,Xn-2,....,X1,X0。
Pow(x, n)表示就x的n次方的值
public class FibonacciProblem {
public static int f1(int n) {//暴力递归
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
return f1(n - 1) + f1(n - 2);
}
public static int f2(int n) {//线性乘法
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int res = 1;
int pre = 1;
int tmp = 0;
for (int i = 3; i <= n; i++) {
tmp = res;
res = res + pre;
pre = tmp;
}
return res;
}
public static int f3(int n) {//数列矩阵乘法
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
// [ 1 ,1 ]
// [ 1, 0 ]
int[][] base = {
{ 1, 1 },
{ 1, 0 }
};
int[][] res = matrixPower(base, n - 2);
return res[0][0] + res[1][0];
}
public static int[][] matrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];
for (int i = 0; i < res.length; i++) {
res[i][i] = 1;
}
// res = 矩阵中的1
int[][] tmp = m;// 矩阵1次方
for (; p != 0; p >>= 1) {
if ((p & 1) != 0) {
res = muliMatrix(res, tmp);
}
tmp = muliMatrix(tmp, tmp);
}
return res;
}
// 两个矩阵乘完之后的结果返回
public static int[][] muliMatrix(int[][] m1, int[][] m2) {
int[][] res = new int[m1.length][m2[0].length];
for (int i = 0; i < m1.length; i++) {
for (int j = 0; j < m2[0].length; j++) {
for (int k = 0; k < m2.length; k++) {
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;
}
public static int s1(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return n;
}
return s1(n - 1) + s1(n - 2);
}
public static int s2(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return n;
}
int res = 2;
int pre = 1;
int tmp = 0;
for (int i = 3; i <= n; i++) {
tmp = res;
res = res + pre;
pre = tmp;
}
return res;
}
public static int s3(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return n;
}
int[][] base = { { 1, 1 }, { 1, 0 } };
int[][] res = matrixPower(base, n - 2);
return 2 * res[0][0] + res[1][0];
}
}
扩展问题——奶牛问题
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。假设第一年就一头老母牛，第二年就2头母牛，第三牛就3头母牛，第四年就4头母牛，第五年就6头。第六年就9头。请编程实现在第n年的时候，共有多少头母牛？
思路：今年的牛的数目=去年的牛的数目+三年前牛的数目 即：f(n)=f(n-1)+f(n-3)
f(n)=f(n-1)+f(n-3)=1*f(n-1)+0*f(n-2)+1*f(n-3) 最后的递推为1*f(n-3) 表示一个3阶问题
|F(N),F(N-1),F(N-2),| = |F(3),F(2),F(1)| * (|3*3|)^N-3 3*3的矩阵的N-3次方
计算出a~i
public static int c1(int n) {//暴力递归
if (n < 1) {
return 0;
}
if (n == 1 || n == 2 || n == 3) {
return n;
}
return c1(n - 1) + c1(n - 3);
}
public static int c2(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2 || n == 3) {
return n;
}
int res = 3;
int pre = 2;
int prepre = 1;
int tmp1 = 0;
int tmp2 = 0;
for (int i = 4; i <= n; i++) {
tmp1 = res;
tmp2 = pre;
res = res + prepre;
pre = tmp1;
prepre = tmp2;
}
return res;
}
public static int c3(int n) {//数列矩阵乘法 O(longN)
if (n < 1) {
return 0;
}
if (n == 1 || n == 2 || n == 3) {
return n;
}
int[][] base = {
{ 1, 1, 0 },
{ 0, 0, 1 },
{ 1, 0, 0 } };
int[][] res = matrixPower(base, n - 3);//乘法可以做到 O(longN)
return 3 * res[0][0] + 2 * res[1][0] + res[2][0];
}
继续扩展-又假如每头牛的寿命只有十年，则 f(n)=f(n-1)+f(n-3)-f(n-10) 表示一个10阶问题
爬楼梯-台阶问题
F(N)=F(N-1)+F(N-2) f(2)=2 f(1)=1
int[][] base = { { 1, 1 }, { 1, 0 } }; res = base^(N-2)
F(N)=2*res[0][0]+ 1*res[1][0]
public static int s1(int n) {//暴力递归 O(2^N)
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return n;
}
return s1(n - 1) + s1(n - 2);
}
public static int s2(int n) {//暴力递归 线性乘法
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return n;
}
int res = 2;
int pre = 1;
int tmp = 0;
for (int i = 3; i <= n; i++) {
tmp = res;
res = res + pre;
pre = tmp;
}
return res;
}
public static int s3(int n) {//数列矩阵乘法 O(longN)
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return n;
}
int[][] base = { { 1, 1 }, { 1, 0 } };
int[][] res = matrixPower(base, n - 2);
return 2 * res[0][0] + res[1][0];
}
给定一个数N，想象只由0和1两种字符，组成的所有长度为N的字符串，如果某个字符串，任何0字符的左边都有1紧挨着，认为这个字符串达标
返回有多少达标的字符串！
- 暴力解
N个长度由0|1组成的字符串的个数 2^N次方个 检验是否有效O(N) 所以总的时间复杂度 O(2^N * N)
- 斐波那契数列-矩阵求法
所以F(N) = F(N-1)+F(N-2) 斐波那契数列求解 F(1)=1 F(2) = 2
