动态规划

动态规划算法学习记录

爬楼梯

点击去力扣 ->>> 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入： 输出： 解释：有两种方法可以爬到楼顶。

  1. 阶 + 阶
  2. 阶

示例 2：

输入： 输出： 解释：有三种方法可以爬到楼顶。

  1. 阶 + 阶 + 阶
  2. 阶 + 阶
  3. 阶 + 阶

提示：

我的解答

采用递归的方式进行编写。每次进行选择都是 和 两种情况，则编写递归函数计算 和 选择的种类数即可。并将数值对应的方式存入 中，使得在递归之前先检查是否已经已存在数据，存在则直接查询返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int climbStairs(int n) {
        if (n == 1){
            return 1;
        }
        HashMap<Integer,Integer> list = new HashMap<>();
        return upLayer(n - 1,list) + upLayer(n - 2,list);
    }

    public int upLayer(int n,HashMap<Integer,Integer> map) {
        if (map.containsKey(n)) {
            return map.get(n);
        }
        if(n == 0) {
            return 1; 
        }
        if(n == 1) {
            return 1;
        }
        int temp = upLayer(n - 1,map) + upLayer(n - 2,map);
        map.put(n,temp);
        return temp;
    }
}

官方解答

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

使用滚动数组实现，这方法太妙了！

斐波那契数

点击去力扣 ->>> 斐波那契数

斐波那契数 （通常用 表示）形成的序列称为 斐波那契数列 。该数列由 和 开始，后面的每一项数字都是前面两项数字的和。也就是：

1
2
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入： 输出： 解释：

示例 2：

输入： 输出： 解释：

示例 3：

输入： 输出： 解释：

提示：

自己解答

思路是使用上一节学到的动态数组，遍历数字从而逐渐累加和，从而得出结果

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int fib(int n) {
        if (n == 0){
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int a = 0, b = 1, c = 1;
        for(int i = 1; i<n -1;i++) {
            a = b;
            b = c;
            c = a + b;
        }
        return c;
    }
}

官方解答

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

方法二：矩阵快速幂

方法一的时间复杂度是 。使用矩阵快速幂的方法可以降低时间复杂度。

首先我们可以构建这样一个递推关系：

​

因此：

​

令：

因此只要我们能快速计算矩阵 的 次幂，就可以得到 的值。如果直接求取 ，时间复杂度是 ，可以定义矩阵乘法，然后用快速幂算法来加速这里 的求取。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n - 1);
        return res[0][0];
    }

    public int[][] pow(int[][] a, int n) {
        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
2
3
4
5
6
7
class Solution {
    public int fib(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
        return (int) Math.round(fibN / sqrt5);
    }
}

下面这哥们面向结果编程🤣🤣🤣

第 N 个泰波那契数

点击去力扣 ->>> 第 N 个泰波那契数

泰波那契序列 定义如下：

, 且在 的条件下

给你整数 ，请返回第 个泰波那契数 的值。

示例 1：

输入：

输出：

解释：

​

示例 2：

输入：

输出：

提示：

  • 答案保证是一个 位整数，即 。

自己解答

思路还是之前的动态数组的方式，与之前的写法几乎相同，只是这次换成了 个数累加而已

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int tribonacci(int n) {
        if(n < 2) {
            return n;
        }
        if (n == 2) {
            return 1;
        }
        int a = 0, b = 1, c = 1, ans = 0;
        for(int i = 3;i<=n;++i) {
            ans = a + b + c;
            a = b;
            b = c;
            c = ans;
        }
        return ans;
    }
}

官方解答

方法一：动态规划

泰波那契数的边界条件是 。当 时，每一项的和都等于前三项的和，因此有如下递推关系：

由于泰波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 、 和 。

根据状态转移方程和边界条件，可以得到时间复杂度和空间复杂度都是 的实现。由于 只和前三项有关，因此可以使用「滚动数组思想」将空间复杂度优化成 。如下的代码中给出的就是这种实现。

fig1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        int p = 0, q = 0, r = 1, s = 1;
        for (int i = 3; i <= n; ++i) {
            p = q;
            q = r;
            r = s;
            s = p + q + r;
        }
        return s;
    }
}

使用最小花费爬楼梯

点击去力扣 ->>> 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

1
2
3
4
5
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

1
2
3
4
5
6
7
8
9
10
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

自己解答

自己的第一思路还是将计算过的值存在HashMap中，然后递归。最终得出的结果不出所料，内存、时间都耗费了非常多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int cost0 = checkCost(0,cost,map);
        int cost1 = checkCost(1,cost,map);
        return cost0 > cost1 ? cost1 : cost0;
    }

    public int checkCost(int now, int[] cost, HashMap<Integer,Integer> map) {
        if (now > cost.length) {
            return 0;
        }
        if(now == cost.length - 1) {
            return cost[now];
        }
        if(map.containsKey(now)) {
            return map.get(now);
        }
        int thisCost = 0;
        if(now < cost.length - 1){
            thisCost = cost[now];
        }
        int cost1 = checkCost(now + 1,cost,map) + thisCost;
        int cost2 = checkCost(now + 2,cost,map) + thisCost;
        int nowCost = cost1 > cost2 ? cost2 : cost1;
        map.put(now,nowCost);
        return nowCost;
    }
}

官方解答

方法一：动态规划

假设数组 的长度为 ，则 个阶梯分别对应下标 到 ，楼层顶部对应下标 ，问题等价于计算达到下标 的最小花费。可以通过动态规划求解。

创建长度为 的数组 ，其中 表示达到下标 的最小花费。

由于可以选择下标 或 作为初始阶梯，因此有 。

当 时，可以从下标 使用 的花费达到下标 ，或者从下标 使用 的花费达到下标 。为了使总花费最小， 应取上述两项的最小值，因此状态转移方程如下：

依次计算 中的每一项的值，最终得到的 ​ 即为达到楼层顶部的最小花费。

代码：

1
2
3
4
5
6
7
8
9
10
11
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];
    }
}

上述代码的时间复杂度和空间复杂度都是 。注意到当 时， 只和 与 有关，因此可以使用滚动数组的思想，将空间复杂度优化到 ​。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

打家劫舍

点击去力扣 ->>> 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

1
2
3
4
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

自己解答

思路是新开一个同样大小的数组，依次遍历原始数组中的数据，将前三个的最大值放入数组中，往后就对比新数组中 i-2 位置 和 i-3 位置的数据谁大，然后加上当前数据存在新数组中。计算完成之后，最大值就在新数组的倒数两个数之中产生。本来代码挺规范的，修修Bug导致堆成了屎山代码🤣🤣🤣

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int rob(int[] nums) {
        int number = nums.length;
        if (number == 1) {
            return nums[0];
        }
        if(number == 2){
            return nums[0] > nums[1] ? nums[0] : nums[1];
        }
        if(number == 3) {
            return nums[0] + nums[2] > nums[1] ? nums[0] + nums[2] : nums[1];
        }
        int[] money = new int[number];
        money[0] = nums[0];
        money[1] = nums[1];
        money[2] = nums[0] + nums[2] > nums[1] ? nums[0] + nums[2] : nums[1];
        for(int i = 3;i<number;++i) {
            int tempMax = money[i - 3] > money[i - 2] ? money[i - 3] : money[i - 2];
            money[i] = nums[i] + tempMax;
        }
        return money[number - 1] > money[number - 2] ? money[number - 1] : money[number - 2];
    }
}

官方解答

点击去力扣 ->>> 打家劫舍解答

删除并获得点数

点击去力扣 ->>> 删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：

1
2
3
4
5
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：

1
2
3
4
5
6
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

提示：

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 104

自己解答

Emmm···，想法是创建一个四个数的数组，然后遍历nums，累加相同的数字，然后把相邻的数字存在数组里，在根据打家劫舍的算法来动态计算。但是没写出来······

官方解答

方法一：动态规划

根据题意，在选择了元素 后，该元素以及所有等于 或 的元素会从数组中删去。若还有多个值为 的元素，由于所有等于 或 的元素已经被删除，我们可以直接删除 并获得其点数。因此若选择了 ，所有等于 的元素也应一同被选择，以尽可能多地获得点数。

记元素 在数组中出现的次数为 ，我们可以用一个数组 记录数组 中所有相同元素之和，即 。若选择了 x，则可以获取 的点数，且无法再选择 和 。这与打家劫舍是一样的，在统计出 数组后，读者可参考打家劫舍中的动态规划过程计算出答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxVal = 0;
        for (int val : nums) {
            maxVal = Math.max(maxVal, val);
        }
        int[] sum = new int[maxVal + 1];
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }

    public int rob(int[] nums) {
        int size = nums.length;
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

复杂度分析

时间复杂度：，其中 是数组 的长度， 是 $nums 中元素的最大值。空间复杂度：O(M)$​。

方法二：排序 + 动态规划

注意到若 中不存在某个元素 ，则选择任一小于 的元素不会影响到大于 的元素的选择。因此我们可以将 排序后，将其划分成若干连续子数组，子数组内任意相邻元素之差不超过 ​。对每个子数组按照方法一的动态规划过程计算出结果，累加所有结果即为答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        int ans = 0;
        Arrays.sort(nums);
        List<Integer> sum = new ArrayList<Integer>();
        sum.add(nums[0]);
        int size = 1;
        for (int i = 1; i < n; ++i) {
            int val = nums[i];
            if (val == nums[i - 1]) {
                sum.set(size - 1, sum.get(size - 1) + val);
            } else if (val == nums[i - 1] + 1) {
                sum.add(val);
                ++size;
            } else {
                ans += rob(sum);
                sum.clear();
                sum.add(val);
                size = 1;
            }
        }
        ans += rob(sum);
        return ans;
    }

    public int rob(List<Integer> nums) {
        int size = nums.size();
        if (size == 1) {
            return nums.get(0);
        }
        int first = nums.get(0), second = Math.max(nums.get(0), nums.get(1));
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = Math.max(first + nums.get(i), second);
            first = temp;
        }
        return second;
    }
}

复杂度分析

时间复杂度：，其中 是数组 的长度。对 排序需要花费 的时间，遍历计算需要花费 的时间，故总的时间复杂度为 。 空间复杂度：。统计 至多需要花费 的空间。