当前位置: 首页 > news >正文

算法设计与分析——动态规划

1.动态规划基础

1.1动态规划的基本思想

        动态规划建立在最优原则的基础上,在每一步决策上列出可能的局部解,按某些条件舍弃不能得到最优解的局部解,通过逐层筛选减少计算量。每一步都经过筛选,以每一步的最优性来保证全局的最优性。具体来说,动态规划算法仍然是将待求解的问题的若干子问题,采用列表技术,将从小到大的子问题的计算答案存储于一张表中,由于将原问题分解后的各个子问题可能存在重复,所以当重复遇到该子问题时,只需要查表继续问题的求解,而不需要重复计算。所以动态规划算法的基本思想是记录子问题并不断填表。

1.2动态规划的基本要素

        通常一个可以用动态规划算法求解的问题应该具有3个要素:最优子结构、无后效性和子问题重叠性。

        最优子结构:动态规划算法的关键在于正确的找出基本的递推关系式和恰当的边界条件。要做到这一点,必须将原问题分解为几个相互联系的阶段,在每一个子问题的求解中,均利用它前面子问题的最优化结果,依次进行,最有一个子问题所得的最优解就是整个问题的最优解。

        无后效性:将各个阶段依次排好之后,一旦某阶段的状态已经确定,它以前各阶段的状态无法直接影响未来的决策,并且当前状态的决策只是对以往决策的总结。

        子问题重叠性:动态规划计算最优值时,每次计算所产生的子问题并不总是新问题,有些问题被重复计算多次,但是动态规划将这些子问题的解存放在表格中,不需要重复计算,提高了程序的效率。

1.3动态规划的基本方法

        动态规划问题千奇百怪,有诸多变种,但是动态规划具有比较鲜明的特征,即最优子结构和重叠子问题。解决动态规划问题的思路很重要,掌握下面五步之后再加以练习能够解决许多动态规划问题。

  1. 确定dp的含义:dp数组中存放的是每个子问题的最优解。
  2. 推导动态转移方程:在动态规划问题中
  3. dp的初始化
  4. 遍历顺序
  5. 打印表格

2.矩阵连乘问题

        给定n个矩阵\left \{ {A_{1},A_{2},...,A_{n}} \right \},其中矩阵A_{i}的维数为p_{i-1}×p_{i},且A_{i}A_{i+1}是可乘的,考察这n个矩阵的连乘积A_{1}A_{2}...A{n}。由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序,这种计算次序可以用加括号的方式来确定。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少?

        设有四个矩阵A、B、C、D,它们的维数分别是:50×10,10×40,40×30,30×5,其完全加括号方式为:(A((BC)D)),(A(B(CD))),((AB)(CD)),(((AB)C)D),((A(BC))D)所需的乘法次数分别为16000,10500,36000,87500,34500。

        对于n个矩阵的连乘积,设其不同的计算次序为p(n)。每种加括号方式都可以分解为两个矩阵的加括号方式:(A_{1}...A_{k})(A_{k+1}...A_{n}),其递推式为:

                                                      p(n)=\sum_{k=1}^{n-1}p(k)p(n-k)

卡特兰数是组合数学中一个常出现在各种计数问题中的数列。其递推式如下:

                                                h(n)=\sum_{k=0}^{n-1}h(k)h(n-k-1)

 该递推关系的解为:C_{n}=\frac{(2n)!}{(n+1)!n!}

 卡特兰数的渐近增长为 C_{n}~\frac{4^{n}}{n^{3/2}\sqrt{\pi }}

2.1分析最优子结构

        设n个矩阵连乘的最佳计算次序为(A_{1}...A_{k})(A_{k+1}...A_{n}),则(A_{1}...A_{k})(A_{k+1}...A_{n})连乘的计算次序都是最优的。矩阵连乘计算次序问题的最优解包含着子问题的最优解。这种性质称为最优子结构性质,问题的最优子结构性质是该问题可用DP方法求解的显著特征。

2.2递归关系建立

        将矩阵连乘积(A_{i}A_{i+1}...A_{j})记为A[i:j],这里i\leqslant jA[i:j]的总计算量为:A[i:k]的计算量加上A[k+1:j]的计算量,再加上A[i:k]A[k+1:j]相乘的计算量。

        设计算A[i:j]的最佳计算次序所对应的乘法次数为m[i:j],则原问题的最优解为m[1:n]

        当i=j时,A[i:j]=A_i,因此m_i=0,i=1,2,...,n

        当i<j时,m[i,j]=min_{i\leqslant k\leqslant j}(m[i,k]+m[k+1,j] + p_{i-1}p_{k}p_{j})

2.3代码分析

#include<stdio.h>
#define N 7
void MatrixChain(int *p,int n,int m[][N],int s[][N])
{for(int i = 0; i <= n; ++i) m[i][i] = 0;//自乘的消耗为0for(int r = 2; r <= n; ++r){for(int i = 1; i <= n - r + 1; ++i){int j = i + r - 1;m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];//试探性的赋值。s[i][j] = i;for(int k = i + 1; k < j; ++k){int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];if(t < m[i][j]){m[i][j] = t;      s[i][j] = k;}}}}
}void Traceback(int i, int j, int s[][N]){if(i == j) printf("A%d",i);else{printf("(");Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);printf(")");}
}      int main()
{int p[N]={30,35,15,5,10,20,24};int m[N][N],s[N][N];MatrixChain(p,N-1,m,s);printf("矩阵的最佳乘积方式为:");Traceback(1,6,s);return 0;
}

3.电路布线问题

        在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,\pi (i))将上端接线柱与下端接线柱相连,如图所示:

                

其中\pi(i)\{1,2,...,n\}的一个排列,导线(i,\pi (i))称为该电路的第i条连线。对于任何1\leqslant i< j\leqslant n,第i条连线和第j条连线相交的充分且必要条件是\pi(i)>\pi(j)

        在制作电路板时,要求将这n条连线分布到若干绝缘层上。在同一层上的连线不可相交。电路布线问题要确定将那些连线安排在第一层上,使得该层上要有尽可能多的连线。换句话说,该问题要确定导线集Nets最大不相交子集

3.1最优子结构分析

        记N(i,j)=\{t|(t,\pi (t))\in Nets,t\leqslant i,\pi (t)\leqslant j \}N(i,j)的最大不相交子集为MNS(i,j)Size(i,j)=|MNS(i,j)|

(1)当i=1时,MNS(1,j)=N(1,j)=\{(1,\pi(1))\}

(2)当i>1时,

        若j<\pi(i)。此时,(i,\pi(i)\nsubseteq N(i,j))。所以N(i,j) = N(i-1,j),从而Size(i,j)=Size(i-1,j)

        若j\geq \pi(i)。此时,

        如果(i,\pi(i)\in MNS(i,j)),则对任意的(t,\pi(t)\in \in MNS(i,j))t<i\pi(t)<\pi(i)。在这种情况下MNS(i,j)-\{(i,\pi(i))\}N(i-1,\pi(i)-1)的最大不相交子集,从而Size(i,j)=Size(i-1,\pi(i)-1)+1

        如果(i,\pi(i)\nsubseteq MNS(i,j)),则对任意的(t,\pi(t)\in \in MNS(i,j)),有t<i。从而MNS(i-1,j)\subseteq N(i,j)。因此,Size(i,j)\geqslant Size(i-1,j)。另一方面有MNS(i,j)\subseteq N(i-1,j),因此又有Size(i,j)\leqslant Size(i-1,j),从而有Size(i,j)= Size(i-1,j)

3.2递归关系建立

(1)当i=1时,Size(1,j)=\left\{\begin{matrix} 0~~~~~ j<\pi(1) & \\ 1~~~~~ j \geqslant\pi(1)& \end{matrix}\right.

(2)当i>1时,

                                Size(i,j)=\left\{\begin{matrix} Size(i-1,j) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~j< \pi(i)& \\ max\{Size(i-1,j),Size(i-1,\pi(i)-1)+1\}~~~~~j\geqslant \pi(i)& \end{matrix}\right.

        电路布线问题的最优值为Size(n,n)

3.3代码分析

void MNS(int C[],int n,int **size)
{for(int j = 0; j < C[1];++j) size[1][j] = 0;for(int j = C[1]; j <= n;++j) size[1][j] = 1;for(int i = 2; i < n; ++i){for(int j = 1; j < C[i]; ++j)    size[i][j] = size[i-1][j];for(int j = C[i]; j <= n; ++j)    size[i][j] = max(size[i-1][j],size[i-1][C[i]-1]+1);}size[n][n] = max(size[n-1][n],size[n-1][C[n]-1]+1);
}

4.最长公共子序列 

        若给定子序列X=\{x_{1},x_{2},...,x_{m}\},则Z=\{z_{1},z_{2},...z_{k}\}是X的子序列是指存在一个严格递增下标序列\{i_{1},i_{2},...i_{k}\}使得对于所有的j=1,2,...,kz_{j}=x_{i_{j}}

        给定两个序列XY,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列XY公共子序列。我们的问题是给定两个序列X=\{x_{1},x_{2},...,x_{m}\}Y=\{y_{1},y_{2},...,y_{n}\},找出XY最长公共子序列

4.1最优子结构分析

        设序列X=\{x_{1},x_{2},...,x_{m}\}Y=\{y_{1},y_{2},...,y_{n}\}的最长公共子序列为Z_{k}=\{z_{1},z_{2},...z_{k}\},则

(1)若x_{m}=y_{n},则z_{k}=x_{m}=y_{n},且Z_{k-1}X_{m-1}Y_{n-1}的最长公共子序列。

(2)若x_{m}\neq y_nz_k\neq x_m,则Z_kX_{m-1}Y_n的最长公共子序列。

(3)若x_{m}\neq y_nz_k\neq y_n,则Z_kX_{m}Y_{n-1}的最长公共子序列。

由此可见,两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此,最长公共子序列问题具有最优子结构性质

4.2递归关系建立

       设二维数组c[i][j]记录序列X_iY_j的最长公共子序列的长度。其中X=\{x_{1},x_{2},...,x_{m}\}Y=\{y_{1},y_{2},...,y_{n}\}。当i=0j=0时,空序列是它们的最长公共子序列,此时c[i][j]=0其它情况下:

        c[i][j]=\left\{\begin{matrix} 0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~i=0~or~j=0\\ c[i-1][j-1]+1~~~~~~~~~~~~~~~~~~i,j>0~and~x_i=y_j\\ max\{c[i][j-1],c[i-1][j]\}~~~~~~i,j>0~and~x_i\neq y_j\end{matrix}\right.

4.3代码分析

void LCSLength()
{for(int i = 1; i <= m; ++i) c[i][0] = 0;//存放各个子问题的最优值for(int j = 1; j <= n; ++j) b[0][j] = 0;//存放各个子问题最优值的来源for(int i = 1; i < m; ++i){for(int j = 1; i <= n; ++j){if(x[i]==y[j]){c[i][j] = c[i-1][j-1] + 1;b[i][j] = 1;}else if(c[i-1][j] >= c[i][j-1]){c[i-1] = c[i-1][j];b[i][j] = 3;}else {c[i][j] = c[i][j-1];b[i][j] = 2;}}}
}

5.图像压缩问题

        图像的变位压缩存储格式将所给的像素点序列\{p_1,p_2,...p_n\},0\leqslant p_i\leqslant 255分割m个连续段S_1,S_2,...,S_m。第i个像素段S_i(1\leqslant i\leqslant m)中,有l[i]个像素,且该段中每个像素都只用b[i]位表示。设t[i]=\sum_{k=1}^{i-1}l[k],则第i个像素段S_i

                                                      S_i=\{p_{t[i]+1},...,p_{t[i]+l[i]}\} ~~~1\leqslant i\leqslant m

h_i=[log(max(p_k)+1)],则h_i\leqslant b[i]\leqslant 8。因此需要用3位表示b[i],如果限制1\leqslant l[i]\leqslant 255,则需要用8位来表示b[i]。因此第i个像素段所需要的存储空间为l[i]*b[i]+11位。按此格式存储像素序列\{p_1,p_2,...p_n\},则需要\sum_{i=1}^{m}l[i]*b[i]+11m位的空间。

        图像压缩问题要求确定像素序列\{p_1,p_2,...p_n\}的最优分段,使得依此分段所需要的存储空间最少。每个分段的长度不超过255位。

5.1最优子结构分析

        设l[i]b[i](1\leqslant i\leqslant m)\{p_1,p_2,...p_n\}的最优分段。显而易见,l[1]b[1]\{p_1,...p_{l[1]}\}的最优分段。图像压缩问题满足最优子结构性质。

        设s[i]1\leqslant i\leqslant n,是像素序列\{p_1,...,p_i\}的最优分段所需的存储位数。

                                        s[i]=min\{s[i-k]+k*bmax(i-k+1,i)\}+11

其中bmax(i,j)=log(max(p_k)+1)

5.2代码分析

void Compress(int n, int p[], int s[], int l[], int b[]) {const int Lmax = 256;const int header = 11;s[0] = 0;for (int i = 1; i <= n; i++) {b[i] = length(p[i]); // 计算像素点 p[i] 需要的存储位数int bmax = b[i];s[i] = s[i - 1] + bmax; // 赋初值l[i] = 1;for (int k = 2; k <= i && k <= Lmax; k++) {if (bmax < b[i - k + 1]) {bmax = b[i - k + 1];}if (s[i] > s[i - k] + k * bmax) {s[i] = s[i - k] + k * bmax;l[i] = k;}}s[i] += header; // 添加头部信息的开销}
}

6.凸多边形最优三角剖分

        凸多边形:一个简单多边形及其内部构成一个闭凸集时,称该简单多边形为凸多边形,即凸多边形边界上或内部的任意两点所连成的直线段上所有点均在凸多边形的内部或边界上。

        为方便描述,用多边形顶点的逆时针序列表示凸多边形,即p=\{v_0,v_1,...v_n\},表示具有n+1条边的凸多边形。  

        若v_iv_j是多边形上的不相邻的两个顶点,则线段v_iv_j称为多边形的一条弦。弦将多边形分割成两个多边形\{v_i,v_{i+1},...v_j\}\{v_j,v_{j+1},...v_i\}

        多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。

        凸多边形的最优三角剖分:给定凸多边形P,以及定义在由多边形的边和弦组成的三角形上的权函数w,要求确定该凸多边形的三角剖分,使得该三角剖分中诸三角形上权之和为最小。

6.1最优子结构分析

        假设存在一个凸多边形的最优剖分P,它的一个子凸多边形Q不是最优剖分。也就是说存在一个代价更小的三角剖分Q^{'}。如果是这样的话,使用Q^{'}替换Q,在保证其它子三角剖分不变的情况下,会产生一个新的整体三角剖分P^{'},它的代价更小,则与P是最优三角剖分的假设矛盾。所以,凸多边形的最优三角剖分具有最优子结构性。

6.2递归关系建立

        定义t[i][j]1\leqslant i\leqslant j\leqslant n为凸子多边形\{v_{i-1},v_i,...,v_j\}的最优三角剖分所对应的权函数值,取其最优值。为方便起见,退化的多边形\{v_{i-1},v_i\}具有权值0。根据此定义,要凸多边形(n+1)P的最有权值为t[1][n]

        t[i][j]的值可以利用最优子结构性质递归地计算。当j-i\geqslant > 1时,凸子多边形至少有3个顶点。由最优子结构性质,t[i][j]的值应为t[i][k]+t[k+1][j]+v_{i-1}v_kv_jv_{i-1}v_kv_j代表该三角形的权值,其中(i\leqslant k \leqslant j-1)。因此

                t[i][j]=\left\{\begin{matrix} 0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~i=j\\ min\{t[i][k]+t[k+1][j]+w(v_{i-1}v_kv_j)\}~~~~~~i<j\end{matrix}\right.

6.3代码分析

        

void MinWeightTriangulation(int *weights, int n) {int t[N][N] = {0}; // 用于存储子问题的最优解int s[N][N] = {0}; // 用于存储分割点// 初始化for (int i = 1; i < n; i++) {t[i][i] = 0;}// 动态规划计算for (int r = 2; r < n; r++) {for (int i = 1; i < n - r + 1; i++) {int j = i + r - 1;t[i][j] = t[i + 1][j] + get_weight(i - 1, i, j, weights);s[i][j] = i;// 尝试所有分割点for (int k = i + 1; k < j; k++) {int u = t[i][k] + t[k + 1][j] + get_weight(i - 1, k, j, weights);if (u < t[i][j]) {t[i][j] = u;s[i][j] = k;}}}}
}

7.0-1背包问题 

        给定n个物品和1个背包。物品i的重量是w_i,其价值为v_i,背包的容量为W。如何选择装入背包的物品,使得装入背包中物品的总价值最大? 通常称物体不可分割的背包问题为0-1背包问题。

        问题的形式化描述为,给定W>0w_i>0v_i>01\leqslant i\leqslant n,要求找出n元0-1向量(x_1,x_2,...,x_n),满足:

                                                        max\sum_{i=1}^{n}v_ix_i

                                                        \left\{\begin{matrix} \sum_{i=1}^{n}w_ix_i\leqslant W\\ x_i\in \{0,1\},1\leqslant i\leqslant n \end{matrix}\right.

7.1最优子结构性分析  

        假设(x_1,x_2,...,x_n)是所给0-1背包问题的已给最优解,则(x_2,...,x_n)是下面相应子问题的一个最优解:

                                                        max\sum_{i=2}^{n}v_ix_i

                                                        \left\{\begin{matrix} \sum_{i=2}^{n}w_ix_i\leqslant W-w_1x_1\\ x_i\in \{0,1\},2\leqslant i\leqslant n \end{matrix}\right.

7.2递归关系建立

        令C[i][j]表示子问题\left\{\begin{matrix} \sum_{k=1}^{i}w_kx_k\leqslant j\\ x_k\in \{0,1\} ~~~~~1\leqslant k\leqslant i \end{matrix}\right.的最优解。C[i-1][j-w_ix_i]表示该问题的子问题\left\{\begin{matrix} \sum_{k=1}^{i-1}w_kx_k\leqslant j-w_ix_i\\ x_k,x_k\in \{0,1\} ~~~~~1\leqslant k\leqslant i-1 \end{matrix}\right.的最优解。        

        最优解的递归关系式为:

                                C[i][0]=c[0][j]=0, ~~1\leqslant i\leqslant n,~~1\leqslant j\leqslant W

                                C[i][j]=\left\{\begin{matrix} C[i-1][j]~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~j<w_i\\ max\{C[i-1][j],C[i-1][j-w_i]+v_i\}~~~j\geqslant w_i \end{matrix}\right.

7.3代码分析

void knapsack(int W, int* p, int *w, int size)
{int C[size][W];//用于存储子问题的最优解for(int i = 0; i < size; ++i)for(int j = 0; j < W; ++j)C[i][j] = 0;for(int i = 1; i < size; ++i)for(int j = 1; j < W; ++j){if(w[i-1] < j){C[i][j]=max(C[i-1][j],C[i-1][j-w[i-1]+p[i-1]);}else C[i][j] = C[i-1][j];}
}

8.最优二叉查找树

        给定n个关键字组成的有序序列S=\{s_1,s_2,...,s_n\},用这些关键字构造一棵二叉查找树 T,该树具有性质:存储于每个节点的元素大于左子树中任一个节点中的元素,小于其右子树中任意节点的元素。

        通常用平均比较次数来作为衡量不同二叉查找树查找效率的标准。设在表示为S=\{s_1,s_2,...,s_n\}的二叉查找树T中,元素s_i的结点深度为c_i(1\leqslant i\leqslant n),查找概率为p_i;虚节点为\{e_0,e_1,...,e_n\}e_j的结点深度为d_j,查找概率为q_j(0\leqslant j\leqslant n)。那么平均比较次数通常被定义为:

                                        C=\sum_{i=1}^{n}p_i(1+c_i)+\sum_{j=0}^{n}q_jd_j

        最优二叉查找树是在所有表示有序序列的二叉查找树中,具有最小平均比较次数的二叉树。

8.1最优子结构分析

        将由实结点\{s_1,s_2,...,s_n\}和虚结点\{e_0,e_1,...,e_n\}构成的二叉查找树记为T(1,n)。设定元素s_k作为该树的根结点,1\leqslant k\leqslant n。则二叉查找树T(1,n)的左子树由实结点\{s_1,s_2,...,s_{k-1}\}和虚结点\{e_0,e_1,...,e_k-1\}组成,记为T(1,k-1),而右子树由实结点\{s_{k-1},...,s_{n}\}和虚结点\{e_{k-1},...,e_{n}\}组成,记为T(k+1,n) 。

        如果T(1,n)是最优二叉查找树,假设它的左子树不是一个最优二叉查找树,也就是说存在另一个二叉查找树有更小的查找次数,那么在右子树不变的情况下,拥有该左子树的二叉查找树的效率比原树更高,那么原树就不是最优二叉查找树。则左子树T(1,k-1)和右子树T(k+1,n)也是最优二叉查找树。

8.2递归关系建立

        设T(1,n)的一棵由实结点\{s_1,s_2,...,s_j\}和虚节点\{e_0,e_1,...,e_j\}构成的最优二叉查找子树为T(i,j),则C'^{}[i][j]表示 T[i][j]的平均比较次数。选定结点作为T[i][j]的根结点,则左子树为T(i,k-1),右子树T(k+1,j),相应的比较次数分别为C'[i][k-1]C'[k+1][j]。用p[n]表示查找实结点的概率,用q[n]表示需节点的查找概率。

                        w_{ij}C'[i][j]=w_{i(k-1)}C'i][k-1]+w_{(k+1)j}C'[k+1][j]+w_{ij}

其中w_{ij}=\sum_{m=i}^{j}p_m+\sum_{i=i-1}^{j}q_t~~~~~1\leqslant i\leqslant j\leqslant n

C[i][j]=w_{ij}C'[i][j]

得到:C[i][j]=w_{ij}+min\{C[i][k-1]+C[k+1][j]\}

其中w_{ij}=w_{i(j-1)}+p_j+q_j

8.3代码分析

#include <iostream>
#include <vector>
#include <climits>using namespace std;void build_optimal_bst(vector<int> s, vector<double> p, vector<double> q) {int n = s.size();// 初始化 C 和 R 数组vector<vector<double>> C(n + 1, vector<double>(n + 1, 0));vector<vector<int>> R(n + 1, vector<int>(n + 1, 0));// 计算 W 数组vector<vector<double>> W(n + 1, vector<double>(n + 1, 0));for (int i = 1; i <= n; ++i) {W[i][i - 1] = q[i - 1];}// 动态规划填充 C 和 R 数组for (int l = 1; l <= n; ++l) {  // 子树长度从1到nfor (int i = 0; i <= n - l; ++i) {int j = i + l;C[i][j] = numeric_limits<double>::max();for (int r = i; r < j; ++r) {double t = W[i][j] + C[i][r] + C[r + 1][j];if (t < C[i][j]) {C[i][j] = t;R[i][j] = r;}}}}// 更新 W 数组for (int l = 1; l <= n; ++l) {for (int i = 0; i <= n - l; ++i) {int j = i + l;W[i][j] = W[i][j - 1] + p[j] + q[j + 1];}}cout << "Cost matrix C:" << endl;for (int i = 0; i <= n; ++i) {for (int j = 0; j <= n; ++j) {cout << C[i][j] << " ";}cout << endl;}cout << "\nRoot position matrix R:" << endl;for (int i = 0; i <= n; ++i) {for (int j = 0; j <= n; ++j) {cout << R[i][j] << " ";}cout << endl;}
}int main() {vector<int> s = {1, 3, 5, 7};  // 有序序列 Svector<double> p = {0.15, 0.1, 0.25, 0.1};  // 查找概率 pvector<double> q = {0.05, 0.15, 0.1, 0.15, 0.05};  // 边界及间隙概率 q// 构建 OBSTbuild_optimal_bst(s, p, q);return 0;
}

        

        

        

        

        

相关文章:

算法设计与分析——动态规划

1.动态规划基础 1.1动态规划的基本思想 动态规划建立在最优原则的基础上&#xff0c;在每一步决策上列出可能的局部解&#xff0c;按某些条件舍弃不能得到最优解的局部解&#xff0c;通过逐层筛选减少计算量。每一步都经过筛选&#xff0c;以每一步的最优性来保证全局的最优性…...

【实战篇】GEO是什么?还可以定义新的数据类型吗?

背景 之前&#xff0c;我们学习了 Redis 的 5 大基本数据类型&#xff1a;String、List、Hash、Set 和 Sorted Set&#xff0c;它们可以满足大多数的数据存储需求&#xff0c;但是在面对海量数据统计时&#xff0c;它们的内存开销很大&#xff0c;而且对于一些特殊的场景&…...

SpringBoot最佳实践之 - 项目中统一记录正常和异常日志

1. 前言 此篇博客是本人在实际项目开发工作中的一些总结和感悟。是在特定需求背景下&#xff0c;针对项目中统一记录日志(包括正常和错误日志)需求的实现方式之一&#xff0c;并不是普适的记录日志的解决方案。所以阅读本篇博客的朋友&#xff0c;可以参考此篇博客中记录日志的…...

【Flutter】状态管理:高级状态管理 (Riverpod, BLoC)

当项目变得更加复杂时&#xff0c;简单的状态管理方式&#xff08;如 setState() 或 Provider&#xff09;可能不足以有效地处理应用中状态的变化和业务逻辑的管理。在这种情况下&#xff0c;高级状态管理框架&#xff0c;如 Riverpod 和 BLoC&#xff0c;可以提供更强大的工具…...

OAK相机的RGB-D彩色相机去畸变做对齐

▌低畸变标准镜头的OAK相机RGB-D对齐的方法 OAK相机内置的RGB-D管道会自动将深度图和RGB图对齐。其思想是将深度图像中的每个像素与彩色图像中对应的相应像素对齐。产生的RGB-D图像可以用于OAK内置的图像识别模型将识别到的2D物体自动映射到三维空间中去&#xff0c;或者产生的…...

smartctl硬盘检查工具

一、smartctl工具简介   Smartmontools是一种硬盘检测工具&#xff0c;通过控制和管理硬盘的SMART(Self Monitoring Analysis and Reporting Technology)&#xff0c;自动检测分析及报告技术)技术来实现的&#xff0c;SMART技术可以对硬盘的磁头单元、盘片电机驱动系统、硬盘…...

清空MySQL数据表

要清空 MySQL 数据表&#xff0c;您可以使用 TRUNCATE 或 DELETE 命令 使用 TRUNCATE 命令 TRUNCATE 命令用于删除表中的所有数据&#xff0c;并重置自增 ID&#xff08;如果存在&#xff09;&#xff1a; TRUNCATE TABLE table_name;将 table_name 替换为您要清空的表的名称…...

2024年妈杯MathorCup大数据竞赛A题超详细解题思路

2024年妈杯大数据竞赛初赛整体难度约为0.6个国赛。A题为台风中心路径相关问题&#xff0c;为评价预测问题&#xff1b;B题为库存和销量的预测优化问题。B题难度稍大于A题&#xff0c;可以根据自己队伍情况进行选择。26日早六点之前发布AB两题相关解题代码论文。 下面为大家带来…...

Kafka系列之:Kafka集群磁盘条带划分和Kafka集群磁盘扩容详细方案

Kafka系列之:Kafka集群磁盘条带划分和Kafka集群磁盘扩容详细方案 一、lsblk命令二、Kafka节点磁盘条带化方案一三、Kafka节点磁盘条带化方案二四、理解逻辑区块LE五、查看kafka节点磁盘条带划分情况六、Kafka节点磁盘扩容一、lsblk命令 lsblk命令用于列出块设备的信息,包括磁…...

【LeetCode】修炼之路-0007- Reverse Integer (整数反转)【python】

题目 Reverse Integer Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0. Assume the environment does not allow you to store 64-b…...

【Flutter】页面布局:线性布局(Row 和 Column)

在 Flutter 中&#xff0c;布局&#xff08;Layout&#xff09;是应用开发的核心之一。通过布局组件&#xff0c;开发者可以定义应用中的控件如何在屏幕上排列。Row 和 Column 是 Flutter 中最常用的两种线性布局方式&#xff0c;用于水平和垂直排列子组件。在本教程中&#xf…...

C语言巨难题:执行操作可获得的最大总奖励 I(C语言版)

1.题目&#xff1a; 给你一个整数数组 rewardValues&#xff0c;长度为 n&#xff0c;代表奖励的值。 最初&#xff0c;你的总奖励 x 为 0&#xff0c;所有下标都是 未标记 的。你可以执行以下操作 任意次 &#xff1a; 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。如果…...

【力扣】GO解决子序列相关问题

文章目录 一、引言二、动态规划方法论深度提炼子序列问题的通用解法模式 三、通用方法论应用示例&#xff1a;最长递增子序列&#xff08;LeetCode题目300&#xff09;Go 语言代码实现 四、最长连续递增序列&#xff08;LeetCode题目674&#xff09;Go 语言代码实现 五、最长重…...

Ubuntu20.04安装VM tools并实现主机和虚拟机之间文件夹共享

1、Ubuntu20.04安装VM tools 参考这个&#xff0c;很详细&#xff1a;Ubuntu 20.04 安装 VMwareTools 教程 2、实现主机与VMware虚拟机共享文件夹 设置共享文件夹参考&#xff1a;windows和虚拟机互传文件的三种方式 挂载操作参考&#xff1a;主机与VMware虚拟机共享文件夹&…...

Linux 学习笔记(十七)—— 文件系统

终极目标&#xff1a;理解 inode 和 软硬连接&#xff1b; 文件系统&#xff1a;Ext2; 文件 文件内容 文件属性; ——> 磁盘上存储的文件 存储的文件内容 存储的文件属性&#xff1b; Linux系统中&#xff1a;文件内容使用数据块存储&#xff0c;文件属性使用inode(固定…...

【计算机网络 - 基础问题】每日 3 题(五十八)

✍个人博客&#xff1a;https://blog.csdn.net/Newin2020?typeblog &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/fYaBd &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞…...

Netty入门基础:IO模型中BIO\NIO概念及区别【附演示代码】

文章目录 &#x1f600;BIO&#x1f4a2;实战demo &#x1f308;NIO&#x1f3cd;Buffer核心属性核心方法 &#x1f397;Channel&#x1f388;Selector核心方法 &#x1f9e8;实战demo &#x1f3a8;粘包与半包 &#x1f600;BIO 传统IO模型&#xff0c;同步阻塞&#xff0c;每…...

vue2 使用环境变量

一. 在根目录下创建.env.xxx文件 .env 基础系统变量&#xff0c;无论何种环境&#xff0c;都可使用其中配置的值&#xff0c;其他环境中的变量会覆盖.env中的同名变量。 .env.development 开发环境 .env.production 生产环境 .env.staging 测试环境 二. 内容格式 vue2 使用是以…...

数据预处理

继续提取代码片段&#xff1a; 12. **导入iris数据集并查看前5行数据**&#xff1a; python from sklearn.datasets import load_iris iris load_iris() X iris.data print(iris数据集的维度为:, X.shape) print(iris数据集的前5行数据为:\n, X[:5]) …...

django宠物领养管理系统-计算机毕业设计源码26858

目录 1 绪论 1.1 选题背景与意义 1.2国内外研究现状 1.3论文结构与章节安排 2系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 3.3.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分析 2.5本章小结 3 系统总体设计 3…...

使用TeamViewer远程局域网内的两台电脑

有个场景&#xff0c;有人还不知道TV可以局域网操作&#xff0c;记录一下。 主要就是修改设置&#xff0c;将取消激活改为接受 然后输入受控端的ip即可...

GUI简介、Swing的常用组件、java程序的运行过程、class文件、JAR、runable_jar、双括号初始化

GUI简介 GUI&#xff1a;图形用户界面&#xff0c;在计算机中采用图形的方式显示用户界面 java的GUI开发 AWT&#xff1a;java最早推出的GUI编程开发包&#xff0c;界面风格跟随操作系统SWT&#xff1a;eclipse就是java使用SWT开发的Swing&#xff1a;在AWT的基础上扩充了功能…...

@Autowired和@Resource和getBean()区别

今天遇到一个对我来说很奇葩的错误&#xff0c;我想在Service中注入bean&#xff0c;我这里使用了Autowired和Resource都不能注入&#xff0c;导致初始化失败&#xff0c;使用了getBean()方法就可以注入。从来没有遇到过这个问题。后来我查询了一下&#xff0c;才明白了原理。我…...

Merlion笔记(四):添加一个新的预测模型

文章目录 1 模型配置类2 模型类3 运行模型&#xff1a;一个简单的例子4 可视化5 定量评估6 定义一个基于预测器的异常检测器 本文提供了一个示例&#xff0c;展示如何向 Merlion 添加一个新的预测模型,遵循 CONTRIBUTING.md 中的说明。建议在阅读本篇文章之前&#xff0c;先查…...

【论文阅读】ESRGAN

学习资料 论文题目&#xff1a;增强型超分辨率生成对抗网络&#xff08;ESRGAN: Enhanced Super-Resolution Generative Adversarial Networks&#xff09;论文地址&#xff1a;[1809.00219] ESRGAN&#xff1a;增强型超分辨率生成对抗网络代码&#xff1a;xinntao / ESRGAN&am…...

电脑异常情况总结

文章目录 笔记本无症状息屏黑屏 笔记本无症状息屏黑屏 &#x1f34e; 问题描述&#xff1a; 息屏导致黑屏&#xff1b;依次操作计算机--》右键--》管理--》事件查看器--》Windows日志--》系统&#xff1b;从息屏到异常黑屏之间出现了很多错误&#xff0c;如下&#xff1a;事件…...

[项目详解][boost搜索引擎#1] 概述 | 去标签 | 数据清洗 | scp

目录 一、前言 二、项目的相关背景 三、搜索引擎的宏观原理 四、搜索引擎技术栈和项目环境 五、正排索引 VS 倒排索引--原理 正排索引 分词 倒排索引 六、编写数据去除标签和数据清洗模块 Parser 1.数据准备 parser 编码 1.枚举文件 EnumFile 2.去标签ParseHtml(…...

PL/I语言的起源?有C语言,有B语言和A语言吗?为什么shell脚本最开始可能有#!/bin/bash字样?为什么不支持嵌套注释?

PL/I语言的起源 在20世纪50~60年代&#xff0c;当时主流的编程语言是COBOL/FORTRAN/ALGOL等&#xff0c;IBM想要设计一门通用的编程语言&#xff0c;已有的编程语言无法实现此要求&#xff0c;故想要设计一门新语言&#xff0c;即是PL/I. PL/I是Programming Language/One的缩写…...

gin入门教程(3):创建第一个 HTTP 服务器

首先设置golang github代理&#xff0c;可解决拉取git包的时候&#xff0c;无法拉取的问题&#xff1a; export GOPROXYhttps://goproxy.io再查看自己的go版本&#xff1a; go version我这里的版本是&#xff1a;go1.23.2 linux/arm64 准备工作做好之后就可以进行开发了 3.…...

Vue+ECharts+iView实现大数据可视化大屏模板

Vue数据可视化 三个大屏模板 样式还是比较全的 包括世界地图、中国地图、canvas转盘等 项目演示&#xff1a; 视频&#xff1a; vue大数据可视化大屏模板...

山石网站超市/ui设计公司

我有一个场景,当我点击按钮时,我想要弹出AlertDialog. AlertDialog是一个自定义警报对话框,因为它具有自定义Listview.我使用以下代码分配AlertDialog OnClick按钮top.setOnClickListener(new OnClickListener() {Context mcontext;Overridepublic void onClick(View arg0) {//…...

wordpress多网站整合在一个后台/广州seo顾问

c中允许在结构体当中定义函数&#xff0c;它的用法和类的用法很像&#xff0c;不过与类有一个区别在于&#xff0c;struct中定义的函数和变量都是默认为public的&#xff0c;但class中的则是默认为private 如&#xff1a; #include<iostream> #include<string> s…...

网站设计高大上/广东深圳疫情最新消息今天

[b]关于后缀名[/b] [quote]*.Z compress程序压缩的文件 *.bz2 bzip2程序压缩的文件 *.gz gzip程序压缩的文件 *.tar tar程序打包的数据&#xff0c;没有经过压缩 *.tar.gz tar程序打包的数据&#xff0c;经过gzip压缩[/quote][b]1、compress[/b] 压缩compress filename 解压缩c…...

旅游网站只做/seo数据分析

介绍 Python代码审计方法多种多样&#xff0c;但是总而言之是根据前人思路的迁移融合扩展而形成。目前Python代码审计思路&#xff0c;呈现分散和多样的趋势。Python微薄研发经验以及结合实际遇到的思路和技巧进行总结&#xff0c;以便于朋友们的学习和参考。 SQL注入和ORM注入…...

制作俄语网站/南宁网站推广营销

传入一个需要比较的字符串。例如 [value compare:"********"] &#xff0c;返回 NSOrderedSame。 options:(NSStringCompareOptions)传入 NSStringCompareOptions 枚举的值 enum{NSCaseInsensitiveSearch 1,//不区分大小写比较NSLiteralSearch 2,//区分大小写比较N…...

唐山网站建设外包公司哪家好/鲜花网络营销推广方案

1. 均值滤波器与中值滤波器 image processing - Difference between linear and non linear filter - Signal Processing Stack Exchange 最为典型的均值滤波器是线性滤波器&#xff0c;而中值滤波器是非线性滤波器。 判断一个函数&#xff08;滤波器&#xff09;线性非线性的最…...