设计商业网站应该做到什么,中国建筑集团有限公司董事长,安康建设网站,免费商用的网站模板贪心算法 回溯算法 分治算法 动态规划
贪心#xff1a;一条路走到黑#xff0c;就一次机会#xff0c;只能哪边看着顺眼走哪边 回溯#xff1a;一条路走到黑#xff0c;无数次重来的机会#xff0c;还怕我走不出来 (Snapshot View) 动态规划#xff1a;拥有上帝视角一条路走到黑就一次机会只能哪边看着顺眼走哪边 回溯一条路走到黑无数次重来的机会还怕我走不出来 (Snapshot View) 动态规划拥有上帝视角手握无数平行宇宙的历史存档 同时发展出无数个未来 (Versioned Archive View)
初识动态规划、动态规划理论、动态规划实战
初识动态规划
动态规划比较适合用来求解最优问题比如求最大值最小值等。可以非常显著地降低时间复杂度提高的执行效率。
0-1背包问题
使用回溯算法
使用回溯法复杂度比较高是指数级别的规律不好找。递归树中的每个节点表是一种状态我们用I,cw来表示。其中i表示将要决策第几个物品是否要装入背包cw表示当前背包中物品的总重量。如2,2表示我们将要决策第2个物品是否要装入背包在决策前背包中的物品总重量是2。 从递归树中可发现有些子问题的求解是重复的如图中f(2,2)和f(3,4)都被重复计算了两次。我们可借助“备忘录”的解决方式记录已经计算好的f(I,cw)当再次计算到重复的f(I,cw)的时候可以直接从备忘录中取出来用就不用在递归计算了这样就可以避免冗余计算。 private int maxW Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight {22463}; // 物品重量
private int n 5; // 物品个数
private int w 9; // 背包承受的最大重量
private boolean[][] mem new boolean[5][10]; // 备忘录默认值false
public void f(int i, int cw) { // 调用f(0, 0)if (cw w || i n) { // cww表示装满了in表示物品都考察完了if (cw maxW) maxW cw;return;}if (mem[i][cw]) return; // 重复状态mem[i][cw] true; // 记录(i, cw)这个状态f(i1, cw); // 选择不装第i个物品if (cw weight[i] w) {f(i1,cw weight[i]); // 选择装第i个物品}
}使用动态规划算法
把整个求解过程分为n个阶段每个阶段会决策一个物品是否放置到背包中。每个物品决策放入或者不放入背包完之后背包中的物品的重量会有很都情况会达到多种不同的状态对应到递归树中就是很多不同的节点。 把每一层重复的状态节点合并只记录不同的状态然后基于上一层的状态集合来推导下一层的状态集合。我们可以通过合并每一层重复的状态这样就保证每一层不同状态的个数都不会超过w个w表示背包的承载重量这就避免了每层状态个数的指数级增长。 用一个二维数组states[n],[w1]来记录每层可以达到的不同状态
第0个下标从0开始编号物品的重量是2要么转入背包要么不装入背包决策完之后会对应背包的两种状态背包中物品的总重量是0或者2。我们用states[0][0]true和states[0][2]true来表示这两种转态。 第1个物品的重量也是2基于之前的背包状态在这个物品决策完之后不同的状态有3个背包中物品总重量分别是0(00)2(02 or 20)4(22)。我们用states[1][0]truestates[1][2]truestates[1][4]true来表示这三种状态。 weight:物品重量n:物品个数w:背包可承载重量
public int knapsack(int[] weight, int n, int w) {boolean[][] states new boolean[n][w1]; // 默认值falsestates[0][0] true; // 第一行的数据要特殊处理可以利用哨兵优化if (weight[0] w) {states[0][weight[0]] true;}for (int i 1; i n; i) { // 动态规划状态转移for (int j 0; j w; j) {// 不把第i个物品放入背包if (states[i-1][j] true) states[i][j] states[i-1][j];}for (int j 0; j w-weight[i]; j) {//把第i个物品放入背包if (states[i-1][j]true) states[i][jweight[i]] true;}}for (int i w; i 0; --i) { // 输出结果if (states[n-1][i] true) return i;}return 0;
}用回溯算法解决这个问题的时间复杂度O(2^n)是指数级的。动态规划方案的时间复杂度是O(n*w)。n表是物品个数w表是背包可以承载的总重量。 尽管动态规划的执行效率比较高但是我们需要额外申请一个n乘以w1的二维数组对空间消耗比较多。所以动态规划是一种空间换时间的解决思路。 但实际上只需要一个大小为w1的一维数组就可以解决这个问题。动态规划状态转移的过程都可以基于这个一维数组来操作。 public static int knapsack2(int[] items, int n, int w) {boolean[] states new boolean[w1]; // 默认值falsestates[0] true; // 第一行的数据要特殊处理可以利用哨兵优化if (items[0] w) {states[items[0]] true;}for (int i 1; i n; i) { // 动态规划for (int j w-items[i]; j 0; --j) {//把第i个物品放入背包if (states[j]true) states[jitems[i]] true;}}for (int i w; i 0; --i) { // 输出结果if (states[i] true) return i;}return 0;
}
0-1背包问题升级版
基础的背包问题只涉及背包的重量和物品重量现在引入物品价值这个一个变量。对于一组不同重量不同价值不可分割的物品在满足背包最大重量限制的前提下背包中可装入物品的总价值最大是多少
采用回溯算法 在递归树中每个节点表示一个状态需要3个变量Icwcv来表示一个状态。其中i表示即将要决策第i个物品是否装入背包cw表示当前背包中物品的总重量cv表示总价值。 在递归树中有几个节点的i和cw是完全相同的比如f(2,2,4)和f(2,2,3)。在背包中物品总重量一样的情况下f(2,2,4)这种状态对应的物品总价值更大可以舍弃f(2,2,3)这种状态只需要沿着f(2,2,4),这条策略线继续往下决策就可以 即对于I,cw相同的不同状态我们只需要保留cv值最大的那个继续递归处理其他状态不予考虑。 private int maxV Integer.MIN_VALUE; // 结果放到maxV中
private int[] items {22463}; // 物品的重量
private int[] value {34896}; // 物品的价值
private int n 5; // 物品个数
private int w 9; // 背包承受的最大重量
public void f(int i, int cw, int cv) { // 调用f(0, 0, 0)if (cw w || i n) { // cww表示装满了in表示物品都考察完了if (cv maxV) maxV cv;return;}f(i1, cw, cv); // 选择不装第i个物品if (cw weight[i] w) {f(i1,cwweight[i], cvvalue[i]); // 选择装第i个物品}
}采用动态规划算法 还是把整个求解过程分为n个状态每个阶段会决策一个物品是否放到背包中。每个决策完之后背包中的物品的总重量以及总价值会有多种情况也就是会达到多种不同的状态。 用一个二维数组states[n][w1]来记录每层可以达到的不同状态。不过这里数组存储的值不在是boolean类型的了而且当前状态对应的最大总价值我们把每一层中I,cw重复的状态节点合并只记录了cv值最大的那个状态然后基于这些状态来推导下一层的状态。 public static int knapsack3(int[] weight, int[] value, int n, int w) {int[][] states new int[n][w1];for (int i 0; i n; i) { // 初始化statesfor (int j 0; j w1; j) {states[i][j] -1;}}states[0][0] 0;if (weight[0] w) {states[0][weight[0]] value[0];}for (int i 1; i n; i) { //动态规划状态转移for (int j 0; j w; j) { // 不选择第i个物品if (states[i-1][j] 0) states[i][j] states[i-1][j];}for (int j 0; j w-weight[i]; j) { // 选择第i个物品if (states[i-1][j] 0) {int v states[i-1][j] value[i];if (v states[i][jweight[i]]) {states[i][jweight[i]] v;}}}}// 找出最大值int maxvalue -1;for (int j 0; j w; j) {if (states[n-1][j] maxvalue) maxvalue states[n-1][j];}return maxvalue;
}动态规划理论
动态规划理论之最优子结构无后效性和重复子问题
1“一个模型三个特征”理论讲解 什么样的问题适合用动态规划来解决 1“一个模型” 它指的是动态规划适合解决的问题的模型“多阶段决策最优解模型”。 一般是用动态规划来解决最优问题而解决问题的过程需要经历多个决策阶段。每个决策阶段都对应一组状态。然后我们寻找一组决策序列经过这组决策序列能够产生最终期望求解的最优值。 2“三个特征” 他们分别是最优子结构无后效性和重复子问题 1最优子结构 最优子结构指的是问题的最优解包含子问题的最优解。即反之讲可以通过子问题的最优解推导出问题的最优解。 若把最优子结构对应到前面定义的动态规划问题模型上也可以理解为后面阶段的状态可以通过前面阶段的状态推导出来。 2无后效性 无后效性有两层含义第一层含义是在推导后面阶段的状态的时候我们只关心前面阶段的状态值不关心这个状态是怎么一步步推导出来的第二层含义是某阶段状态一旦确定就不受之后阶段的决策影响无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型基本上都会满足无后效性。 3重复子问题 不同的决策序列到达某个相同的阶段时可能会产生重复的状态
两种动态规划解题思路总结 解决动态规划问题一般有两种思路分别可叫作状态转移表法和状态转移方程法 用回溯算法来解决这个问题。如果你自己写一下代码画一下递归树就会发现递归树中有重复的节点。重复的节点表示从左上角到节点对应的位置有多种路线这也能说明这个问题中存在重复子问题。 如果我们走到 (i, j) 这个位置我们只能通过 (i-1, j)(i, j-1) 这两个位置移动过来也就是说我们想要计算 (i, j) 位置对应的状态只需要关心 (i-1, j)(i, j-1) 两个位置对应的状态并不关心棋子是通过什么样的路线到达这两个位置的。而且我们仅仅允许往下和往右移动不允许后退所以前面阶段的状态确定之后不会被后面阶段的决策所改变所以这个问题符合“无后效性”这一特征。 刚刚定义状态的时候我们把从起始位置 (0, 0) 到 (i, j) 的最小路径记作 min_dist(i, j)。因为我们只能往右或往下移动所以我们只有可能从 (i, j-1) 或者 (i-1, j) 两个位置到达 (i, j)。也就是说到达 (i, j) 的最短路径要么经过 (i, j-1)要么经过 (i-1, j)而且到达 (i, j) 的最短路径肯定包含到达这两个位置的最短路径之一。换句话说就是min_dist(i, j) 可以通过 min_dist(i, j-1) 和 min_dist(i-1, j) 两个状态推导出来。这就说明这个问题符合“最优子结构”。
1状态转移表法 回溯法-〉递归树-〉重复子问题-〉备忘录/动态规划 一般能用动态规划解决的问题都可以使用回溯算法的暴力搜索解决。所以当拿到问题时可以先用简单的回溯算法解决然后定义状态每个状态表示一个节点然后对应画出递归树。 从递归树中很容易可以看出是否存在重复子问题以及重复子问题是如何产生的。以此来寻找规律看是否能用动态规划解决。 找到重复子问题之后有两种处理思路**第一种是直接用回溯加“备忘录”的方法来避免重复子问题。**从执行效率上来将这和动态规划的解决思路没有差别第二种是使用动态规划的解决方法状态转移表法。 回溯 private int minDist Integer.MAX_VALUE; // 全局变量或者成员变量
// 调用方式minDistBacktracing(0, 0, 0, w, n);
public void minDistBT(int i, int j, int dist, int[][] w, int n) {// 到达了n-1, n-1这个位置了这里看着有点奇怪哈你自己举个例子看下if (i n j n) {if (dist minDist) minDist dist;return;}if (i n) { // 往下走更新ii1, jjminDistBT(i 1, j, distw[i][j], w, n);}if (j n) { // 往右走更新ii, jj1minDistBT(i, j1, distw[i][j], w, n);}
}递归树
重复子问题
备忘录/动态规划 public int minDistDP(int[][] matrix, int n) {int[][] states new int[n][n];int sum 0;for (int j 0; j n; j) { // 初始化states的第一行数据sum matrix[0][j];states[0][j] sum;}sum 0;for (int i 0; i n; i) { // 初始化states的第一列数据sum matrix[i][0];states[i][0] sum;}for (int i 1; i n; i) {for (int j 1; j n; j) {states[i][j] matrix[i][j] Math.min(states[i][j-1], states[i-1][j]);}}return states[n-1][n-1];
}状态转移表法 先画出一个状态表状态表一般都是二维的其中每个状态包含三个变量行列数组值。我们根据决策的先后过程从前往后根据递推关系分阶段填充状态表中的每个状态。最后将这个递推填表的过程翻译成代码就是动态规划代码了。
状态转移方程法 状态转移方程有点类似递归的解题思路需要分析某个问题如何通过子问题来递归求解也就是所谓的最优子结构。根据最优子结构写出递归公式也就是所谓的状态转移方程。有了状态转移方程代码实现就非常简单了一般情况下有两种代码实现的方法一种是递归加“备忘录”另一种是迭代递推。 private int[][] matrix {{1359}, {2134}{5267}{6843}};
private int n 4;
private int[][] mem new int[4][4];
public int minDist(int i, int j) { // 调用minDist(n-1, n-1);if (i 0 j 0) return matrix[0][0];if (mem[i][j] 0) return mem[i][j];int minLeft Integer.MAX_VALUE;if (j-1 0) {minLeft minDist(i, j-1);}int minUp Integer.MAX_VALUE;if (i-1 0) {minUp minDist(i-1, j);}int currMinDist matrix[i][j] Math.min(minLeft, minUp);mem[i][j] currMinDist;return currMinDist;
}状态转移方程是解决动态规划的关键如果能写出状态转移方程那动态规划问题基本上就解决一大半了但是很多动态规划问题的状态本身就不好定义状态转移方程也就更不好想到。
状态转移表法解题思路大致可以概括为回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。 状态转移方程法的大致思路可以概括为找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码。
动态规划实战
实现搜索引擎中的拼写纠错功能
编辑距离
莱文斯坦距离Levenshtein distance和最长公共子串长度Longest common substring length。其中莱文斯坦距离允许增加、删除、替换字符这三个编辑操作最长公共子串长度只允许增加、删除字符这两个编辑操作。
莱文斯坦距离Levenshtein distance 最长公共子串长度 当用户在搜索框内输入一个拼写错误的单词时我们就拿这个单词跟词库中的单词一一进行比较计算编辑距离将编辑距离最小的单词作为纠正之后的单词提示给用户。 [笔记整理来源 王争 数据结构与算法之美](htt ps://s1.ax1x.com/2020/08/03/aUh2TS.png)
