力扣动态规划基础版（斐波那契类型）
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];
}
}