70. 爬楼梯
https://leetcode.cn/problems/climbing-stairs/
70.爬楼梯
方法一 动态规划
考虑转移方程和边界条件：
f（x） = f（x -1） + f（x - 2）;f（1） = 1；f（2） = 2；
class Solution {public int climbStairs(int n) {//到第一阶的方法int p = 1;//到第二阶的方法int q = 2;if(n == 1){return p;}else if(n ==2){return q;}else{int r = 3;for(int i = 3; i <= n; i++){r = q + p;p = q;q = r;}return r;}}
}时间复杂度为O（n）
方法二 矩阵快速幂
需要构造一下 ，对于齐次线性传递
class Solution {public int climbStairs(int n) {int [][] q= {{1,1},{1,0}};int[][] res = pow(n,q);return res[0][0];}//做一个矩阵的乘方public int[][] pow(int n,int[][] a){//做一个单位矩阵int[][] ret = {{1,0},{0,1}};while(n > 0){//用到一个位运算if((n & 1) == 1){ret = multiply(ret,a);}n >>= 1;a = multiply(a,a);}return ret;}//根据构造的矩阵定义public int[][] multiply(int a[][],int b[][]){int c[][] = new int[2][2];for(int i = 0; i < 2; i++){for(int j = 0;j < 2;j++){c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];}}return c;}
}关于为什么第一个元素就是结果：
这里如果麻烦一点的话，假如这个初始向量不是1，1那你可以先用这个操作，然后最后×初始向量，但是要重新定义一个函数就是1*2的矩阵和2*2的矩阵相乘的方法
509.斐波那契数
509. 斐波那契数https://leetcode.cn/problems/fibonacci-number/
方法一 动态规划
和爬楼梯的转移条件都是一模一样的
class Solution {public int fib(int n) {int p = 0,q = 1,r = 0;if(n < 2){return n;}else{for(int i = 2; i <= n; i++){r = p + q;p = q;q = r;}return r;}}
}方法二 矩阵快速幂
和爬楼梯唯一的不同点就是主函数要用n -1
class Solution {public int fib(int n) {if (n < 2) {return n;}int r[][] = {{1,1},{1,0}};int res[][] = pow(n - 1,r);return res[0][0];}public int[][] pow(int n ,int[][] c){int [][]r = {{1,0},{0,1}};while(n > 0){if((n & 1) == 1){r = mul(r,c);}n >>= 1;c = mul(c,c);}return r;}public int[][] mul(int a[][],int b[][]){int r[][] = new int[2][2];for(int i = 0; i < 2; i++){for(int j = 0;j < 2; j++){r[i][j] = a[i][0] * b[0][j] + a[i][1]*b[1][j];}}return r;}}
1137.第N个泰伯那契数
1137. 第 N 个泰波那契数https://leetcode.cn/problems/n-th-tribonacci-number/
方法一 动态规划
class Solution {public int tribonacci(int n) {int p = 0,q = 1,r = 1;if(n == 0){return 0;}else if(n == 1){return 1; }else if(n == 2){return 1;}else{for(int i = 3; i <= n; i++){int m = p + q + r;p = q;q = r;r = m;}return r;}}
}class Solution {public int tribonacci(int n) {int p = 0,q = 1,r = 1;if(n == 0){return 0;}else if(n == 1){return 1; }else if(n == 2){return 1;}else{for(int i = 3; i <= n; i++){int m = p + q + r;p = q;q = r;r = m;}return r;}}
}746.使用最小花费爬楼梯
746. 使用最小花费爬楼梯https://leetcode.cn/problems/min-cost-climbing-stairs/分析一手核心问题还是找到这个状态转移方程
dp[i] = Math.min(dp[i -1] + cost[i -1], dp[i -2] + cost[i -2]);class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int[] dp = new int[n + 1];dp[0] = dp[1] = 0;for(int i = 2;i <= n;++i){dp[i] = Math.min(dp[i -1] + cost[i -1], dp[i -2] + cost[i -2]);}return dp[n];}
}时间：O（n） 空间O（n），可以发现第i项只和i -1 和i -2相关，所以可以用一个滚轮降低空间复杂度
class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int[] dp = new int[n + 1];int pre = 0; int cur = 0;for(int i = 2;i <= n;++i){int nex = Math.min(cur + cost[i - 1],pre + cost[i - 2]);pre = cur;cur = nex;}return cur;}
}这样的话空间复杂度就是O（1）了
198.打家劫舍
198. 打家劫舍https://leetcode.cn/problems/house-robber/核心还是去找边界条件和这个状态转移方程，这个题目状态转移方程没以前那么好想两种假设：
1.偷窃第k间房屋，就不能偷窃第k - 1间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。
2.不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。
边界条件：dp[0]的话就是nums【0】，dp【1】的话就是两个最大的、
状态转移方程：
dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i]);class Solution {public int rob(int[] nums) {if(nums == null){return 0;}int length = nums.length;if(length == 1){return nums[0];}int[] dp = new int[length];dp[0] = nums[0];dp[1] = Math.max(nums[0],nums[1]);for(int i = 2; i < length; i++){dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i]);}return dp[length -1];}
}模仿上一道题，这个题也能变成轮询的问题，降低空间复杂度
class Solution {public int rob(int[] nums) {if(nums == null){return 0;}int length = nums.length;if(length == 1){return nums[0];}if(length == 2){return Math.max(nums[0],nums[1]);}int pre = nums[0];int cur = Math.max(nums[0],nums[1]);for(int i = 2; i < length; i++){int nex = Math.max(cur,pre + nums[i]);pre = cur;cur = nex;}return cur;}
}740.删除并获得点数
740. 删除并获得点数https://leetcode.cn/problems/delete-and-earn/题目有一点晦涩难懂，看了题解以后恍然大悟，发现就是一个乱序的打家劫舍哈哈哈，需要找出这个最大值，做一个数组，再用打家劫舍的函数就解决了，这个第一次做有点难想到动态规划
class Solution {public int deleteAndEarn(int[] nums) {int Maxval = 0;for(int val : nums){Maxval = Math.max(val,Maxval);}int [] sums = new int[Maxval + 1];//for(int val : nums){sums[val] += val;}return rob(sums);}
//纯打家劫舍public int rob(int[] nums){int n = nums.length;int dp[] = new int[n];dp[0] = nums[0];dp[1] = Math.max(nums[0],nums[1]);for(int i = 2; i < n; ++i){dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i]);}return dp[n - 1];}
}
