# algorithm **Repository Path**: equant-yiguang/algorithm ## Basic Information - **Project Name**: algorithm - **Description**: No description available - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2021-08-10 - **Last Updated**: 2025-02-25 ## Categories & Tags **Categories**: Uncategorized **Tags**: 算法 ## README --- typora-copy-images-to: img --- # algorithm # 算法 ## 前要知识 什么是拓扑排序（Topological Sorting）：https://www.jianshu.com/p/b59db381561a ## 一.概念 #### 参考 ``` 五大常用算法之一：分治算法 五大常用算法之二：动态规划算法 五大常用算法之三：贪心算法 五大常用算法之四：回溯法 五大常用算法之五：分支限界法 https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html 字典树 算法设计与分析（第2版） 21世纪大学本科计算机专业系列教材 王晓东 第2章 递归与分治策略 2.1 递归的概念 2.2 分治法的基本思想 2.3 二分搜索技术 2.4 大整数的乘法 2.5 Strassen矩阵乘法 2.6 棋盘覆盖 2.7 合并排序 2.8 快速排序 2.9 线性时间选择 2.10 接近点对问题 2.11 循环赛日程表 小结 习题 第3章 动态规划 3.1 矩阵连乘问题 3.2 动态规划算法的基本要素 3.3 长公共子序列 3.4 凸多边形优三角剖分 3.5 多边形游戏 3.6 图像压缩 3.7 电路布线 3.8 流水作业调度 3.9 0-1背包问题 3.10 优二叉搜索树 小结 习题 第4章 贪心算法 4.1 活动安排问题 4.2 贪心算法的基本要素 4.2.1 贪心选择性质 4.2.2 优子结构性质 4.2.3 贪心算法与动态规划算法的差异 4.3 优装载 4.4 哈夫曼编码 4.4.1 前缀码 4.4.2 构造哈夫曼编码 4.4.3 哈夫曼算法的正确性 4.5 单源短路径 4.5.1 算法基本思想 4.5.2 算法的正确性和计算复杂性 4.6 小生成树 4.6.1 小生成树性质 4.6.2 Prim算法 4.6.3 Kruskal算法 4.7 多机调度问题 4.8 贪心算法的理论基础 4.8.1 拟阵 4.8.2 带权拟阵的贪心算法 4.8.3 任务时间表问题 小结 习题 第5章 回溯法 第6章 分支限界法 第7章 概率算法 第8章 NP完全性理论 第9章 近似算法 ``` #### 递归 1. 从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为递归。 2. 不是算法，是一种结构或过程 3. 自顶向下 4. 任何递归形式的算法都能通过栈、队列等数据结构转化为非递归的形式。 #### 递推算法 1. 递推算法是一种用若干步可重复运算来描述复杂问题的方法。递推是序列计算中的一种常用算法。通常是通过计算机前面的一些项来得出序列中的指定象的值。 如想知道一个国家有多少人，可以从村行政级开始，依次往镇、县、市、省向上汇报，到国家这个级别就能找到一个国家有多少人 2. 自底向上 #### 广度优先搜索算法 1. 广度优先搜索算法（Breadth-First Search，缩写为 BFS），又称为宽度优先搜索，是一种图形搜索算法。简单的说，BFS 是从根结点开始，沿着树的宽度遍历树的结点。如果所有结点均被访问，则算法中止。 #### 深度优先搜索算法 1. 深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次. #### 回溯算法 1. 回溯算法是对树形或者图形结构执行一次深度优先遍历，实际上类似枚举的搜索尝试过程，在遍历的过程中寻找问题的解。 深度优先遍历有个特点：当发现已不满足求解条件时，就返回，尝试别的路径。此时对象类型变量就需要重置成为和之前一样，称为**「状态重置」**。 许多复杂的，规模较大的问题都可以使用回溯法，有「通用解题方法」的美称。实际上，回溯算法就是暴力搜索算法，它是早期的人工智能里使用的算法，借助计算机强大的计算能力帮助我们找到问题的解。 2. 状态重置：回溯的关键不在于递归，而在于“状态”。在回溯算法向前的每一步，你都会去设置某个状态，而当向前走走不通的时候回退，此时需要把之前设置的状态撤销掉。 3. 实现 - 回溯算法 = **树的**深度优先搜索 + 剪枝函数 #### 动态规划DP ##### 介绍 1. 动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。 动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归（记忆化搜索），自底向上就是递推。 使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。 ##### 三大步骤 动态规划，无非就是利用**历史记录**，来避免我们的重复计算。而这些**历史记录**，我们得需要一些**变量**来保存，一般是用**一维数组**或者**二维数组**来保存。下面我们先来讲下做动态规划题很重要的三个步骤， 1. **第一步骤**：定义**数组元素的含义**，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？ 2. **第二步骤**：找出**数组元素之间的关系式**，我觉得动态规划，还是有一点类似于我们高中学习时的**归纳法**的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2].....dp[1]，来推出 dp[n] 的，也就是可以利用**历史数据**来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。 3. **第三步骤**：找出**初始值**。学过**数学归纳法**的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是**所谓的初始值**。 ##### 分类 1. 目录 ``` 线性DP； 区间DP； 背包DP； 树形DP； 状态压缩DP； 数位DP； 计数型DP； 递推型DP； 概率型DP； 博弈型DP； 记忆化搜索； 1. 线性DP 最经典单串： 300. 最长上升子序列 (LIS) 最经典双串： 1143. 最长公共子序列 (LCS) 经典问题： 120. 三角形最小路径和 53. 最大子序和 152. 乘积最大子数组 887. 鸡蛋掉落 (DP+二分) 354. 俄罗斯套娃信封问题 (隐晦的LIS) 打家劫舍系列: (打家劫舍3 是树形DP) 198. 打家劫舍 213. 打家劫舍 II 股票系列: 121. 买卖股票的最佳时机 122. 买卖股票的最佳时机 II 123. 买卖股票的最佳时机 III 188. 买卖股票的最佳时机 IV 309. 最佳买卖股票时机含冷冻期 714. 买卖股票的最佳时机含手续费 字符串匹配系列 72. 编辑距离 44. 通配符匹配 10. 正则表达式匹配 2. 区间DP 516. 最长回文子序列 730. 统计不同回文子字符串 1039. 多边形三角剖分的最低得分 664. 奇怪的打印机 312. 戳气球 3. 背包DP 416. 分割等和子集 (01背包-要求恰好取到背包容量) 494. 目标和 (01背包-求方案数) 322. 零钱兑换 (完全背包) https://www.cnblogs.com/mfrank/p/10803417.html 518. 零钱兑换 II (完全背包-求方案数) 474. 一和零 (二维费用背包) 4. 树形DP 124. 二叉树中的最大路径和 1245. 树的直径 (邻接表上的树形DP) 543. 二叉树的直径 333. 最大 BST 子树 337. 打家劫舍 III 那么树形DP有什么作用呢？下面引出三种最版的题 最大独立子集：没有上司的晚会 树的重心 树的直径 5. 状态压缩DP 464. 我能赢吗 526. 优美的排列 935. 骑士拨号器 1349. 参加考试的最大学生数 6. 数位DP 233. 数字 1 的个数 902. 最大为 N 的数字组合 1015. 可被 K 整除的最小整数 7. 计数型DP 计数型DP都可以以组合数学的方法写出组合数，然后dp求组合数 62. 不同路径 63. 不同路径 II 96. 不同的二叉搜索树 (卡特兰数) 1259. 不相交的握手 (卢卡斯定理求大组合数模质数) 8. 递推型DP 所有线性递推关系都可以用矩阵快速幂做，可以O(logN)，最典型是斐波那契数列 70. 爬楼梯 509. 斐波那契数 935. 骑士拨号器 957. N 天后的牢房 1137. 第 N 个泰波那契数 9. 概率型DP 求概率，求数学期望 808. 分汤 837. 新21点 10. 博弈型DP 策梅洛定理，SG定理，minimax 翻转游戏 293. 翻转游戏 294. 翻转游戏 II Nim游戏 292. Nim 游戏 石子游戏 877. 石子游戏 1140. 石子游戏 II 井字游戏 348. 判定井字棋胜负 794. 有效的井字游戏 1275. 找出井字棋的获胜者 11. 记忆化搜索 本质是 dfs + 记忆化，用在状态的转移方向不确定的情况 329. 矩阵中的最长递增路径 576. 出界的路径数 12. 序列DP 模板题：https://leetcode.cn/problems/word-break/solution/by-ac_oier-gh00/ ``` #### 记忆化搜索 1. 记忆化搜索的实质是动态规划，记忆化算法在求解的时候还是按着自顶向下的顺序 2. 记忆化搜索实际上是递归来实现的，但是递归的过程中有许多的结果是被反复计算的，这样会大大降低算法的执行效率。 而记忆化搜索是在递归的过程中，将已经计算出来的结果保存起来，当之后的计算用到的时候直接取出结果，避免重复运算，因此极大的提高了算法的效率。 思路是递归搜索，由当前状态向可能的状态搜索，当前状态的结果=几个下一个状态搜索结果的和。 示例：斐波那契数列，可以简要理解递归以及记忆化搜索 #### 贪心算法 1. 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择，就能得到问题的答案。贪心算法需要充分挖掘题目中条件，没有固定的模式，解决有贪心算法需要一定的**直觉和经验**。 贪心算法不是对所有问题都能得到整体最优解。能使用贪心算法解决的问题具有「贪心选择性质」。「贪心选择性质」严格意义上需要数学证明。能使用贪心算法解决的问题必须具备「无后效性」，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 #### 分治算法 #### 分支限界法 ## 二.区别 #### 递归与递推的区别 结论 1. 从程序上看，递归表现为自己调用自己，递推则没有这样的形式。 2. 递归是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题，是逆向的 递推是从简单问题出发，一步步的向前发展，最终求得问题。是正向的。 3. 递归中，问题的n要求是计算之前就知道的，而递推可以在计算中确定，不要求计算前就知道n。 4. 一般来说，递推的效率高于递归（当然是递推可以计算的情况下） 5. 能有递归的就可以用递推，反之却不行 示例 1. 示例一：斐波那契数列 已知f(1) = 1 , f(2) = 1 , 且满足关系式f(n) = f(n-1) + f(n-2)，则f(50)等于多少？ 分析：根据初始条件f(1) = 1 , f(2) = 1 和关系式f(n) = f(n-1) + f(n-2)，可知，f(3) = f(2) + f(1) , f(3) = f(2) + f(1) ……. 编写代码（递归） ``` public class Fibonacci { static int fun(int n){ if(n == 1 || n == 2){ return 1 ; }else{ return fun(n-1) + fun(n-2) ; } } public static void main(String[] args) { for(int i = 1 ; i <= 15 ; ++i) System.out.println(fun(i)); } } ``` 编写代码（递推、动态规划之递推） ``` static int fun2(int n){ int a[] = new int[20] ; a[1] = 1 ; a[2] = 1 ; for(int i=3 ; i<=n ;i++){ a[i] = a[i-1] + a[i-2] ; } return a[n] ; } ``` 2. 示例二：计算1+2+3+......+100 分析：递归关系为f(n) = f(n-1) + n ，递归出口为f(1) = 1 ; 编写代码（递归）： ``` public class Sum { static int fun(int n){ if( n == 1){ return 1 ; }else{ return fun(n-1) + n ; } } public static void main(String[] args) { // TODO Auto-generated method stub System.out.println(fun(100)); // 5050 } } ``` 编写代码（递推）： ``` static int fun2(int n){ int a[] = new int [200] ; a[1] = 1 ; for(int i=2 ; i<=n ; i++){ a[i] = a[i-1] + i ; } return a[n] ; } ``` 3. 示例三：爬楼问题：假设有n阶楼梯，每次可爬1阶或2阶，则爬到第n层有几种方案？ 分析：假设一阶时只有一种方案f(1) = 1 ; 二阶时有两种方案（即一次走一阶和一次走两阶）f(2) = 2 ;三阶时有3种 f(3) = 3 ;四阶时有五种 f(5) = 5 ;发现递归规律f(n) = f(n-1) + f(n-2) ; 递归出口为f(1) = 1、f(2) = 2 ; 编写代码（递归）： ``` public class Ladder { static int fun(int n){ if(n == 1){ return 1 ; }else if(n == 2){ return 2 ; }else{ return fun(n-1) + fun(n-2) ; } } public static void main(String[] args) { // TODO Auto-generated method stub System.out.println(fun(5)); } } ``` 编写代码（递推）： ``` static int fun2(int n){ int a[] = new int [200] ; a[1] = 1 ; a[2] = 2 ; for(int i=3 ; i<=n ;i++){ a[i] = a[i-1] + a[i-2] ; } return a[n] ; } ``` #### 递归与记忆化搜索的关系 1. 示例一：斐波那契数列 ``` /* * 斐波那契数列 * 由来认识递归、记忆化搜索（回溯）和动态规划 * 记忆化搜索和动态规划：https://www.jianshu.com/p/763302ad5c01 */ public class FibonacciSeries { static long[] arr; public static void main(String[] args) { Long time1 = System.currentTimeMillis(); System.out.println(memorySearch(100)); Long time2 = System.currentTimeMillis(); System.out.println(time2-time1); System.out.println(dp(100)); Long time3 = System.currentTimeMillis(); System.out.println(time3-time2); //总结：普通递归函数性能很差，动态规划性能最好，记忆化搜索次之， //因为记忆化搜索在递归调用中花费更多时间 } /** * 递归函数：存在大量重复运算 */ public static Long ordinary(int n) { if(n==1||n==2) { return 1L; } Long result = ordinary(n-1) + ordinary(n-2); return result; } /** * 动态规划之记忆化搜索 * 浪费太多资源做重复的事情，很自然就会想到能不能加个缓存，将结果存储在缓存中，下次求该值，先去缓存中寻找，找到直接返回，找不到再去计算，这种思想就是记忆化搜索 * 算法复杂度O(n)，自顶向下即记忆化递归 * 斐波那契数的边界条件是 F(0)=0 和 F(1)=1。当 n>1 时，每一项的和都等于前两项的和，因此有如下递推关系： * F(n)=F(n-1)+F(n-2) * 由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0)和 F(1)。 */ public static Long memorySearch(int n) { if(n<=2) { return 1L; } if(Objects.isNull(arr)) { arr = new long[n]; arr[0] = 1L; arr[1] = 1L; } if(arr[n-1] == 0L) { arr[n-1] = memorySearch(n-1)+memorySearch(n-2); } return arr[n-1]; } /** * 动态规划之递推 * 动态规划：将原问题拆解成若干个子问题,同时保存子问题的答案,使得每个子问题只求解一次, * 时间复杂度O(n)，自底向上就是递推 * 状态转移方程： * 用 dp[i] 表示数列的第n项，那么就有如下的状态转移方程： * dp[i]=dp[i-1]+dp[i-2] */ public static Long dp(int n) { if(n<=2) { return 1L; } long[] arr = new long[n]; arr[0] = 1L; arr[1] = 1L; for(int i=2; i> levelOrder(TreeNode root) { List> result = new ArrayList(); Queue queue = new LinkedList(); if(root==null) { return result; } queue.offer(root); while(!queue.isEmpty()) { List temp = new ArrayList(); int currentLevelSize = queue.size(); for(int i=0; i> combine(int n, int k) { List> result = new ArrayList(); List currentResult = new ArrayList(); backtrack(result, currentResult, n, k, 1); return result; } private static void backtrack(List> result, List currentResult, int n, int k, int index) { // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp if (currentResult.size()+(n-index+1) < k) { return; } for(int i=index; i<=n; i++) { List temp = new ArrayList(currentResult); if(temp.size()+1 == k) { temp.add(i); result.add(temp); continue; } temp.add(i); backtrack(result, temp, n, k, i+1); } } ``` #### 动态规划 ##### 模板 ``` 总结一下： 状态定义（建数组） 状态转移方程（数组存值） 写出状态转移方程 如： 用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程： dp[i]=max(dp[i-2]+nums[i], dp[i-1]) 写出边界条件 如边界条件为： dp[0]=nums[0] 只有一间房屋，则偷窃该房屋 dp[1]=max(nums[0],nums[1]) 只有两间房屋，选择其中金额较高的房屋进行偷窃 最终的答案即为 dp[n−1]，其中 n 是数组的长度。 ``` ##### 经典例题 ###### 斐波那契数列 ``` 剑指 Offer 10- I. 斐波那契数列 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下： F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 /** * 递归函数：存在大量重复运算 */ public static Long ordinary(int n) { if(n==1||n==2) { return 1L; } Long result = ordinary(n-1) + ordinary(n-2); return result; } /** * 动态规划之记忆化搜索 * 浪费太多资源做重复的事情，很自然就会想到能不能加个缓存，将结果存储在缓存中，下次求该值，先去缓存中寻找，找到直接返回，找不到再去计算，这种思想就是记忆化搜索 * 算法复杂度O(n)，自顶向下即记忆化递归 * 斐波那契数的边界条件是 F(0)=0 和 F(1)=1。当 n>1 时，每一项的和都等于前两项的和，因此有如下递推关系： * F(n)=F(n-1)+F(n-2) * 由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0)和 F(1)。 */ public static Long memorySearch(int n) { if(n<=2) { return 1L; } if(Objects.isNull(arr)) { arr = new long[n]; arr[0] = 1L; arr[1] = 1L; } if(arr[n-1] == 0L) { arr[n-1] = memorySearch(n-1)+memorySearch(n-2); } return arr[n-1]; } /** * 动态规划之递推 * 动态规划：将原问题拆解成若干个子问题,同时保存子问题的答案,使得每个子问题只求解一次, * 时间复杂度O(n)，自底向上就是递推 * 状态转移方程： * 用 dp[i] 表示数列的第n项，那么就有如下的状态转移方程： * dp[i]=dp[i-1]+dp[i-2] */ public static Long dp(int n) { if(n<=2) { return 1L; } long[] arr = new long[n]; arr[0] = 1L; arr[1] = 1L; for(int i=2; i=0; j--) { temp = temp+nums[j]; if(temp>dp[i]) { dp[i] = temp; } } max = Math.max(max, dp[i]); } return max; } /** * 优化之后 * 时间复杂度：O(m) * 空间复杂度：O(1) */ public static int maxSubArray2(int[] nums) { int pre=0, max=nums[0]; for(int x : nums) { pre = Math.max(pre+x, x); // 上一个数+当前数与当前数的比较 max = Math.max(pre, max); } return max; } 示例 1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 public static void main(String[] args) { int[] nums = {-2,1,-3,4,-1,2,1,-5,4}; System.out.println(maxSubArray2(nums)); } ``` ###### 152.乘积最大子数组 ``` /** * 152. 乘积最大子数组 * 时间复杂度：O(n) * 空间复杂度：O(n) */ public static int maxProduct(int[] nums) { int max = nums[0]; int[] minDp = new int[nums.length]; int[] maxDp = new int[nums.length]; minDp[0] = nums[0]; maxDp[0] = nums[0]; for(int i=1; i= minDp[i-1]*nums[i] && maxDp[i-1]*nums[i]>0) { maxDp[i] = maxDp[i-1]*nums[i]; minDp[i] = Math.min(minDp[i-1]*nums[i], nums[i]); }else if(maxDp[i-1]*nums[i] < minDp[i-1]*nums[i] && minDp[i-1]*nums[i]>0) { maxDp[i] = minDp[i-1]*nums[i]; minDp[i] = Math.min(maxDp[i-1]*nums[i], nums[i]); }else { maxDp[i] = nums[i]; minDp[i] = Math.min(maxDp[i-1]*nums[i], minDp[i-1]*nums[i]); } max = Math.max(max, maxDp[i]); } return max; } /* 2,-5,-2,-4,3 2 -5 20 8 24 2 -10 -2 -80 -240 */ /* 示例 1: 输入: nums = [2,-5,-2,-4,3] 输出: 24 解释: 子数组 [-2,-4,3] 有最大乘积24。 思路: 每个索引位置的乘积最大值为（上一个索引值的最大值或者最小值【因为有负数的情况，负负得正】与当前索引位置的乘积）或者（当前索引位置的值） */ public static void main(String[] args) { int[] nums = {2,-5,-2,-4,3}; System.out.println(maxProduct(nums)); } ``` 优化 ``` public static int maxProduct(int[] nums) { int max = nums[0]; int[] minDp = new int[nums.length]; int[] maxDp = new int[nums.length]; minDp[0] = nums[0]; maxDp[0] = nums[0]; for(int i=1; i> triangle) { int min = Integer.MAX_VALUE; int[] dp = new int[triangle.size()]; for(int i=0; i floors = triangle.get(i); for(int j=floors.size()-1; j>=0; j--) { Integer current = floors.get(j); if(j==0) { dp[j] = dp[j] + current; }else if(j==floors.size()-1) { dp[j] = dp[j-1] + current; }else { dp[j] = Math.min(dp[j], dp[j-1]) + current; } if(i==triangle.size()-1) { if(dp[j] f1 = new ArrayList(); f1.add(2); List f2 = new ArrayList(); f2.add(3); f2.add(4); List f3 = new ArrayList(); f3.add(6); f3.add(5); f3.add(7); List f4 = new ArrayList(); f4.add(4); f4.add(1); f4.add(8); f4.add(3); List> triangle = new ArrayList(); triangle.add(f1); triangle.add(f2); triangle.add(f3); triangle.add(f4); System.out.println(minimumTotal(triangle)); } ``` ###### 打家劫舍 198 > 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 > > 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 > > > > 示例 1： > > 输入：[1,2,3,1] > 输出：4 > 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 > 偷窃到的最高金额 = 1 + 3 = 4 。 > 示例 2： > > 输入：[2,7,9,3,1] > 输出：12 > 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 > 偷窃到的最高金额 = 2 + 9 + 1 = 12 。 > > > 提示： > > 1 <= nums.length <= 100 > 0 <= nums[i] <= 400 > > 来源：力扣（LeetCode） > 链接：https://leetcode.cn/problems/house-robber > 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ##### 二维数组dp ###### 62.不同路径 ``` 问题描述 62. 不同路径 https://leetcode.cn/problems/unique-paths/ 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？ 步骤一、定义数组元素的含义 由于我们的目的是从左上角到右下角一共有多少种路径，那我们就定义 dp[i] [j]的含义为：当机器人从左上角走到(i, j) 这个位置时，一共有 dp[i] [j] 种路径。那么，dp[m-1] [n-1] 就是我们要的答案了。 注意，这个网格相当于一个二维数组，数组是从下标为 0 开始算起的，所以 右下角的位置是 (m-1, n - 1)，所以 dp[m-1] [n-1] 就是我们要找的答案。 步骤二：找出关系数组元素间的关系式 想象以下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达 一种是从 (i-1, j) 这个位置走一步到达 一种是从(i, j - 1) 这个位置走一步到达 因为是计算所有可能的步骤，所以是把所有可能走的路径都加起来，所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。 步骤三、找出初始值 显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的，相当于计算机图中的最上面一行和左边一列。因此初始值如下： dp[0] [0….n-1] = 1; // 相当于最上面一行，机器人只能一直往右走 dp[0…m-1] [0] = 1; // 相当于最左面一列，机器人只能一直往下走 三个步骤都写出来了，直接看代码 public static int uniquePaths(int m, int n) { if (m <= 0 || n <= 0) { return 0; } int[][] dp = new int[m][n]; // // 初始化 for(int i = 0; i < m; i++){ dp[i][0] = 1; } for(int i = 0; i < n; i++){ dp[0][i] = 1; } // 推导出 dp[m-1][n-1] for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; } O(n*m) 的空间复杂度可以优化成 O(min(n, m)) 的空间复杂度的，不过这里先不讲 案例 4：编辑距离 这次给的这道题比上面的难一些，在 leetcdoe 的定位是 hard 级别。好像是 leetcode 的第 72 号题。 问题描述 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 示例： 输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 解答 还是老样子，按照上面三个步骤来，并且我这里可以告诉你，90% 的字符串问题都可以用动态规划解决，并且90%是采用二维数组。 步骤一、定义数组元素的含义 由于我们的目的求将 word1 转换成 word2 所使用的最少操作数 。那我们就定义 dp[i] [j]的含义为：当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]。 有时候，数组的含义并不容易找，所以还是那句话，我给你们一个套路，剩下的还得看你们去领悟。 步骤二：找出关系数组元素间的关系式 接下来我们就要找 dp[i] [j] 元素之间的关系了，比起其他题，这道题相对比较难找一点，但是，不管多难找，大部分情况下，dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。因为我们的目标就是，**从规模小的，通过一些操作，推导出规模大的。对于这道题，我们可以对 word1 进行三种操作 插入一个字符 删除一个字符 替换一个字符 由于我们是要让操作的次数最小，所以我们要寻找最佳操作。那么有如下关系式： 一、如果我们 word1[i] 与 word2 [j] 相等，这个时候不需要进行任何操作，显然有 dp[i] [j] = dp[i-1] [j-1]。（别忘了 dp[i] [j] 的含义哈）。 二、如果我们 word1[i] 与 word2 [j] 不相等，这个时候我们就必须进行调整，而调整的操作有 3 种，我们要选择一种。三种操作对应的关系试如下（注意字符串与字符的区别）： （1）、如果把字符 word1[i] 替换成与 word2[j] 相等，则有 dp[i] [j] = dp[i-1] [j-1] + 1; （2）、如果在字符串 word1末尾插入一个与 word2[j] 相等的字符，则有 dp[i] [j] = dp[i] [j-1] + 1; （3）、如果把字符 word1[i] 删除，则有 dp[i] [j] = dp[i-1] [j] + 1; 那么我们应该选择一种操作，使得 dp[i] [j] 的值最小，显然有 dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1; 于是，我们的关系式就推出来了， 步骤三、找出初始值 显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n] 和所有的 dp[0….m] [0]。这个还是非常容易计算的，因为当有一个字符串的长度为 0 时，转化为另外一个字符串，那就只能一直进行插入或者删除操作了。 代码如下 public int minDistance(String word1, String word2) { int n1 = word1.length(); int n2 = word2.length(); int[][] dp = new int[n1 + 1][n2 + 1]; // dp[0][0...n2]的初始值 for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1; // dp[0...n1][0] 的初始值 for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1; // 通过公式推出 dp[n1][n2] for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { // 如果 word1[i] 与 word2[j] 相等。第 i 个字符对应下标是 i-1 if (word1.charAt(i - 1) == word2.charAt(j - 1)){ p[i][j] = dp[i - 1][j - 1]; }else { dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1; } } } return dp[n1][n2]; } ``` #### 记忆化搜索 ##### 经典例题 1. 斐波那契数 ``` /* * 斐波那契数列 * 由来认识递归、记忆化搜索（回溯）和动态规划 * 记忆化搜索和动态规划：https://www.jianshu.com/p/763302ad5c01 */ public class FibonacciSeries { static long[] arr; public static void main(String[] args) { Long time1 = System.currentTimeMillis(); System.out.println(memorySearch(100)); Long time2 = System.currentTimeMillis(); System.out.println(time2-time1); System.out.println(dp(100)); Long time3 = System.currentTimeMillis(); System.out.println(time3-time2); //总结：普通递归函数性能很差，动态规划性能最好，记忆化搜索次之， //因为记忆化搜索在递归调用中花费更多时间 } /** * 递归函数：存在大量重复运算 */ public static Long ordinary(int n) { if(n==1||n==2) { return 1L; } Long result = ordinary(n-1) + ordinary(n-2); return result; } /** * 动态规划之记忆化搜索 * 浪费太多资源做重复的事情，很自然就会想到能不能加个缓存，将结果存储在缓存中，下次求该值，先去缓存中寻找，找到直接返回，找不到再去计算，这种思想就是记忆化搜索 * 算法复杂度O(n)，自顶向下即记忆化递归 * 斐波那契数的边界条件是 F(0)=0 和 F(1)=1。当 n>1 时，每一项的和都等于前两项的和，因此有如下递推关系： * F(n)=F(n-1)+F(n-2) * 由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0)和 F(1)。 */ public static Long memorySearch(int n) { if(n<=2) { return 1L; } if(Objects.isNull(arr)) { arr = new long[n]; arr[0] = 1L; arr[1] = 1L; } if(arr[n-1] == 0L) { arr[n-1] = memorySearch(n-1)+memorySearch(n-2); } return arr[n-1]; } /** * 动态规划之递推 * 动态规划：将原问题拆解成若干个子问题,同时保存子问题的答案,使得每个子问题只求解一次, * 时间复杂度O(n)，自底向上就是递推 * 状态转移方程： * 用 dp[i] 表示数列的第n项，那么就有如下的状态转移方程： * dp[i]=dp[i-1]+dp[i-2] */ public static Long dp(int n) { if(n<=2) { return 1L; } long[] arr = new long[n]; arr[0] = 1L; arr[1] = 1L; for(int i=2; i wordDict) { // aabccddaa // 0 //1 1 // 0 //1 1 // 0 // 1 1 // 0 // 0 // 1 1 // aa aabc cd cddaa Set words = new HashSet(wordDict); boolean[] dp = new boolean[s.length()+1]; dp[0] = true; for(int i=1; i<=s.length(); i++) { for(int j=0; j=nums.length-1) { return true; } return false; } /* 2,3,1,1,4 当前位置能跳的索引位置 2,4,4,4,8 示例 1： 输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 */ public static void main(String[] args) { int[] nums = {2,3,1,1,4}; System.out.println(canJump(nums)); } ``` ###### 45. 跳跃游戏 II ``` /** * 45. 跳跃游戏 II * 时间复杂度：O(n) * 空间复杂度：O(1) * 思路：与跳跃游戏I不同在于，不是大于了当前最大距离就跳，而是当前能跳的距离内，能跳到最远的距离时才跳 * 如： * 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 索引 * 7, 0, 9, 6, 9, 6, 1, 7, 9, 0, 1, 2, 9, 0, 3 数组 nums * 7 * 11 13 14(跳) * 0 - - - - - - 7 起跳点与跳的最大距离为一个回合，一个回合只准跳一次 */ public static int jump(int[] nums) { if(nums.length==1) { return 0; } int max = nums[0]; int count = 1; boolean isJump = false; // 一个回合内是否跳过 int tempMax = nums[0]; // 当前回合符合起跳的最远距离的暂存值，当前回合结束后取最大值。如上述列子索引2就符合起跳，且最远距离为11 for(int n=0; n=nums.length-1) { return count; } if(n+nums[n]>max) { if(!isJump) { count++; // 一个回合加一次起跳 isJump = true; } tempMax = Math.max(tempMax, n+nums[n]); } if(n==max) { // 准备进入下一回合 isJump = false; // 重置是否起跳 max = tempMax; // 当前回合结束能跳的最远距离 } } return count; } /* 示例 1: 输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。   从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 */ public static void main(String[] args) { int[] nums = {2,2,1,1,4}; System.out.println(jump(nums)); } ``` ###### 121.买卖股票的最佳时机 I ``` /** * 121. 买卖股票的最佳时机 * 方法1：暴力法 * 时间复杂度：O(n2)，循环运行了n(n-1)/2次 * 空间复杂度：O(1) * 思路：求出每个工作日买入，之后的每个工作日卖出所获得收益，取最大 * 超出时间限制 */ public static int maxProfit1(int[] prices) { int profit = 0; // 收益 for(int n=0; nbuy) { // 是否卖出 for(int m=n; mprofit) { profit = profit1+profit2; } } return profit; } /** * 优化 * 123. 买卖股票的最佳时机 III * 时间复杂度：O(n2)，循环运行了n(n-1)/2次 * 空间复杂度：O(1) * 思路：遍历每个交易日，并用该交易日将所有交易日分为两段，分别求前后两段最大利润，取和。结果取最大 */ public static int maxProfit2(int[] prices) { int[] dp1 = new int[prices.length]; int[] dp2 = new int[prices.length]; int profit = 0; // 收益 int min1 = Integer.MAX_VALUE; int profit1 = 0; int max2 = Integer.MIN_VALUE; int profit2 = 0; // 每个工作日结束最大收益 for(int n=0; n=0; n--) { max2 = Math.max(max2, prices[n]); profit2 = Math.max(profit2, max2-prices[n]); dp2[n] = profit2; } for(int n=0; n0) { array2.remove(0); num--; } } public static void main(String[] args) throws Throwable{ //1.根据输入流获取月份、日期和信息 Scanner sc = new Scanner(System.in); //如何获取控制台多行数据 String line1 = sc.nextLine(); String line2 = sc.nextLine(); //一个或多个空格分割字符串：String的split方法支持正则表达式；正则表达式\s表示匹配任何空白字符，+表示匹配一次或多次。 String[] per=line1.split("\\s+"); int mouth=Integer.valueOf(per[0]); int date=Integer.valueOf(per[1]); //2.初始化字母数组 String[] A9 = new String[]{"A","B","C","D","E","F","G","H","I"}; String[] J9 = new String[]{"J","K","L","M","N","O","P","Q","R"}; String[] S9 = new String[]{"S","T","U","V","W","X","Y","Z","*"}; List array=new LinkedList(); array.add(A9); array.add(J9); array.add(S9); //3.先根据月份转移 int data=mouth-1; while(data>2) { data=data-3; } move(array,data); //4.根据月份转移后的三组字母 List l1=new LinkedList(); List l2=new LinkedList(); List l3=new LinkedList(); for(String str:array.get(0)) { l1.add(str); } for(String str:array.get(1)) { l2.add(str); } for(String str:array.get(2)) { l3.add(str); } //5.根据日期转移 int data2=date-1; while(data2>8) { data2=data2-9; } move(l1,data2); move(l2,data2); move(l3,data2); //6.找字母 char[] str= line2.toCharArray(); String[] aa=new String[str.length]; for(int i=0;i 问题描述： > > 给定一个整数数组，返回两个数字的索引，使它们相加的值等于一个特定的目标值。假设对于每个输入只有一种解决方案，并且您不可以两次同时使用相同的元素。 > > 问题的示例： > > 给定nums = [2,7,11,15]， target = 9， > > 因为nums[0] + nums[1] = 2 + 7 = 9，返回[0,1]。 > > 要求：算法时间复杂度为n ``` public class TwoSum { public static void main(String[] args) { int[] arr= {1,2,3,4,5,6,7,8,9}; int target=8; List re=twoSum1(arr,target); for(Object ob:re) { System.out.println(ob.toString()); } } //暴力解决方式,空间复杂度为数组的长度n,时间复杂度为n*n public static List twoSum1(int[] arr,int target) { List al=new ArrayList(); for(int i=0;ii) { list.add(i+"-"+map.get(bbb)); } } return list; } } ``` ##### 6.动态规划 - N步台阶问题 > 题目分析 > 问题本质：斐波那契数列 > > 令跳法为f(n)， > > 如果n=1：{{1}}，f(1)=1； > > 如果n=2：{{1,1},{2}}，f(2)=2； > > 如果n=3，{{1,1,1}，{1,2}，{2,1}}，f(3)=3； > > 如果n=6，有两种情况：1)目前在5阶，跳1步到6；2)目前在4阶，跳2步到6。即f(6)=f(5)+f(4)； > > ... ... > > 如果有n阶(n>2)，1)目前在n-1阶，跳1步到n；2)目前在n-2阶，跳2步到n。即f(n)=f(n-1)+f(n-2)。 > > 实现 > 实现算法往往是简单的，及时是复杂算法也花费不了太多精力，所以将问题转换为数学问题是一种很好的选择。当前这种简单算法实现方式更为简单，而且往往不止一种方式。 ##### 7.螺旋矩阵 54. 螺旋矩阵 https://leetcode.cn/problems/spiral-matrix/ 59. 螺旋矩阵 II https://leetcode.cn/problems/spiral-matrix-ii/