动态规划

动态规划概述

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分解成若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。

贪心算法

贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

回溯

回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。

回溯是递归的副产品，只要有递归就会有回溯。

回溯法并不是什么⾼效的算法，如果想让回溯法⾼效⼀些，可以加⼀些剪枝的操作，但也改不了回溯法就是穷举的本质。

回溯法解决的问题可以概括如下：

• 组合问题：N个数⾥⾯按⼀定规则找出k个数的集合
• 切割问题：⼀个字符串按⼀定规则有⼏种切割⽅式
• ⼦集问题：⼀个N个数的集合⾥有多少符合条件的⼦集
• 排列问题：N个数按⼀定规则全排列，有⼏种排列⽅式
• 棋盘问题：N皇后，解数独等等

二叉树

定义

在计算机科学中，二叉树是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作左子树或右子树。二叉树的分支具有左右次序，不能随意颠倒。

在图论中的定义

二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根节点的度不大于2。有了根节点之后，每个顶点定义了唯一的父节点，和最多2个子节点。然而，没有足够的信息来区分左节点和右节点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

栈/队列

栈

栈是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为栈顶，top）进行加入数据（push）和移除数据（pop）。因而按照后进先出（LIFO, Last In First Out）的原理运作，栈常用一维数组或链表来实现。常与另一种有序的线性数据集合队列相提并论。

栈使用两种基本操作：

• 入栈：将元素放入栈的顶端。
• 出栈：将栈顶端的元素移除。
  

双指针

双指针技术是一种以受控的方式遍历数据集（通常是数组或列表）的技术。它包括两个指针，一个指向数据集的开头，另一个指向数据集的结尾，并根据特定条件将它们相互移动。这种技术通常用于解决涉及在数据集中搜索特定条件或模式的问题，或者需要对数据集中的不同元素进行比较的问题。

双指针技术主要用于解决具有线性时间复杂度的问题，与暴力解法相比，它可以大大提高性能。使用该技术解决的一些常见问题包括：

• 查找一组数据中的最大/最小值。
• 计算特定元素的出现次数。
• 查找没有重复字符的最长子串。
• 查找大小为k的子数组的最大和。

字符串

字符串是由零个或多个字符组成的有限序列。

习题

反转字符串

344: 反转字符串
541: 反转字符串II

替换数字

卡码网54: 替换数字