力扣动态规划基础版（斐波那契类型）

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];}
}