Estom的博客

动态规划——线性动态规划 主要用来熟练动态规划的步骤 斐波那契数列 青蛙跳台阶 最大子段和 1 斐波那契数列问题描述 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下： 12F(0) = 0,   F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 链接 问题分析问题分类 数组 动态规划+迭代 选择策略 数组 动态规划 原理： 以斐波那契数列性质f(n+1)=f(n)+f(n−1) 为转移方程。 算法设计 状态定义： 设$dp$为一维数组，其中 $dp[i]$ 的值代表 斐波那契数列第 $i$个数字 。 转移方程： $dp[i + 1] = dp[i] + dp[i - 1]$，即对应数列定义 $f(n + 1) = f(n) + f(n - ...

作业调度问题 参考文献 https://zhuanlan.zhihu.com/p/30705914 问题描述有n个作业需要在2台机器M1 和M2组成的流水线上完成加工。每个作业都必须先在 M1 上加工，然后在 M2 上加工。M1和M2加工作业i所需的时间分别记作 a_i和b_i，每台机器同一时间最多只能执行一个作业。 请确定这n个作业的最优加工顺序，使得从第一个作业在机器上开始加工，到最后一个作业在机器上加工完成所需的时间最少。 问题分析算法设计 johnson不等式。满足min{bi,aj}>= min{bj,ai}则表示i和j满足johnson不等式。则意味着i在j前执行，不会使的结果变坏。 查参考文献。 算法分析 时间复杂度O(nlogn)按json不等式排序的时间复杂度。 算法实现

投资问题问题描述m元钱，n个项目。f_i(x)表示x元钱投入项目i的效益。求最大效益。 问题分析算法设计 问题分解划分阶段：规模增长的方向有两个。第一个是投资的金额想，第二个是项目选择k。x,k阶段。 确定状态变量dp[x][k]表示投资x，第k个项目的最大收益。 确定状态转移方程。 状态转移过程。 算法效率 O(n*m^2) 算法实现

1 二维数组的查找问题描述 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 链接 问题分析 与一维查找类似。找到中间数字，每次移动可以舍弃掉一半的数字。由于给定的二维数组具备每行从左到右递增以及每列从上到下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。 从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。 从二维数组的左下角开始查找。具有完全一致的效果。 问题分类 线性数据结构 枚举法 查找问题 策略选择算法设计 若数组为空，返回 false 初始化行下标为 0，列下标为二维数组的列数减 1 重复下列步骤，直到行下标或列下标超出边界 获得当前下标位置的元素 num 如果 num 和 target 相等，返回 true 如果 num 大于 target，列下标减 1 如果 num 小于 target，行下标加 1 循环体执行...

迷宫问题1 矩阵中的路径问题描述 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。 123[["a","b","c","e"],["s","f","c","s"],["a","d","e","e"]] 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。 链接 问题分析 最典型的回溯剪枝算法。 问题分类 二维数组，矩阵 回溯剪枝、dfs、递归 迷宫问题 策略选择 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符...

课程概要 C++ 基础基本完成了。包括C++基础、标准库、面向对象。 分类说明A类：基本算法： 包含9种算法思想。每一种算法思想下，应该有至少是个算法的典型样例。用来讲解该算法的工作过程。这些算法样例必须为该算法思想的超级经典样例。并且不再收录到问题类型算法当中。 B类：数据结构算法： 数据结构目录下主要是数据结构的基础知识。包括遍历、搜索、建立、插入、删除等基本操作，主要用来实现数据的存储结构和逻辑结构，以及数据的规则。 数据结构算法目录下。主要是针对4种数据结构的通用算法。在遍历、搜索、插入、删除的基础上进行的额外的通用的算法。与数据结构强相关的通用算法。放到数据结构算法中。 C类：问题类型算法 包含6种问题。主要用来针对特定的问题。关键是这些问题有的时候没办法进行很好的归类。需要在题目里给出标签？不不不。在问题描述前的最上方。给出问题标签。

概述 一个问题。强相关的标签有三个。属于哪一类问题。使用哪些算法思想。问题属于哪一种数据结构。因为vscode的文件组织方式为树形结构。只能支持单一索引，无法支持多种类别的标签索引。 所以最终决定。应该将不断增长的爆炸性问题。转移到C类：问题算法中。主要用来记录在解决问题中的思考和见解。根据问题类型对算法分类。记录算法。 分类说明 与数据结构强相关的算法 与算法思想强相关的算法 与问题目标强相关的算法 命名说明 以某一类算法的名称命名，而不是某一个算法命名。收集找到该类别下的相关算法。