2021-04-08 LeetCode动态规划--斐波那契数列_问题a: 动态规划-fib数列

动态规划算法

算法核心

Those who cnnot remrember the past are condemned to repeat it.
动态规划算法的核心就是记住已经解决过的子问题的解。

动态规划的两种形式

• 自顶向下的备忘录法
  以斐波那契数列为例子，备忘录方法的思想就是创建一个n+1大小的数组来保存求出的斐波那契数列中的每一个值，在递归的过程中如果发现前面fib(n)的值计算出来了就不再计算，如果未计算出来，那么计算出来之后保存在Memo数组中，下次再调用fib(n)的时候就不会重新递归了。
• 自底向上的动态规划
  备忘录法还是利用了递归，备忘录法在计算fib(6)的时候最后还是要计算出fib(1)、fib(2)、fib(3)...，那么我们可以先计算出fib(1)、fib(2)、fib(3)...，这就是动态规划的核心，先解决子问题，再由子问题计算父问题。
  自底向上方法也是利用数组保存了先计算的值，为后面的调用服务。
  一般来说由于备忘录方式的动态规划使用了递归，递归的时候会产生额外的开销，使用自底向上的动态规划要比备忘录方法好。

动态规划的原理

如果问题涉及到了重叠子问题和最优子结构，我们就使用动态规划。

• 最优子结构
  用动态规划求解最优化问题的第一步就是刻画最优解的结构。问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解，就称此问题具有最优子结构性质。因此，某个问题是否适用于动态规划算法，就看他是否具有最优子结构的性质。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考察最优解中用到的所有子问题。
• 重叠子问题
  在斐波那契数列问题中，可以看到大量的重叠子问题，比如在求解fib(6)时，fib(2)被调用了5次。如果使用递归算法的时候会反复求解相同的子问题，不同的调用函数，而不是产生新的子问题，反复求解相同的子问题，就称为具有重叠子问题。在动态规划中使用数组来保存子问题的解，这样子问题多次求解的时候就可以直接查表不用调用函数的递归了。

动态规划的经典模型

最重要的是状态转移方程。

• 线性模型
• 区间模型
• 背包模型

动态规划可以处理的题目类型

• 斐波那契数列问题
• 矩阵路径问题
• 数组区间问题
• 分割整数问题
• 最长递增子序列问题
• 最长公共子序列问题
• 0-1背包问题
• 股票交易问题
• 字符串编辑问题

题目

70.爬楼梯

题目大意

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解题思路

注意出口值，当i等于1时，如果出现dp[2]=2就会出现数组下标越界的情况。

代码实现

class Solution {
    public int climbStairs(int n) {
        //动态规划
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

198. 打家劫舍

题目大意

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

解题思路

当数组只有一个元素的时候，如果用dp数组就会出现数组下标越界。

代码实现

class Solution {
    public int rob(int[] nums) {
        //动态规划
        int n=nums.length;
        int pre1=0,pre2=0,cur=0;
        for(int i=0;i<n;i++){
            cur=Math.max(pre2+nums[i],pre1);
            pre2=pre1;
            pre1=cur;
        }
        return cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

213. 打家劫舍 II

题目大意

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。
在这里插入图片描述

解题思路

环装排列意味着第一个房子和最后一个房子只能偷其中的一个，因此可以把环状问题转化为两个单排列问题：

1. 不偷第一个房子，偷最后一个房子
2. 偷第一个房子，不偷最后一个房子

代码实现

class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        if(n==0){
            return 0;
        }
        if(n==1){
            return nums[0];
        }
        return Math.max(robHouse(nums,0,n-2),robHouse(nums,1,n-1));
    }
    public int robHouse(int[] nums,int l,int r){
        int pre1=0,pre2=0,cur=0;
        for(int i=l;i<=r;i++){
            cur=Math.max(pre1+nums[i],pre2);
            pre1=pre2;
            pre2=cur;
        }
        return cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21