小桥流水78

这个屌丝很懒，什么也没留下！

热门标签

动态规划一：动态规划算法如何设计_写出设计动态规划算法的主要步骤。

作者：小桥流水78 | 2024-07-17 00:37:36

踩

写出设计动态规划算法的主要步骤。

目录

  历史
  概念

初探

  性质
  记忆化搜索
  动态规划算法如何设计？

加深理解

  DAG最短路径
  最长上升子序列
  最长公共子序列
  最大子段和
  上楼梯

DP题目

  实现目标：论文查重、拼写纠错、寻找最近加油站

历史

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

20 世纪 50 年代初美国数学家 R.E.Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。

多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按某种顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。

初探

最优化原理其实就是问题的最优解子结构性质。

假设我们有无限数量面值为 1、5、10 的硬币，凑成面值为 15 的硬币，请问最少需要几个硬币？

思考 2min...

15 的组合，

15 = 10 + 5
15 = 5 + 5 + 5
15 = 10 + 1 + 1 + 1 + 1 +1
......

大家应该想到了，用 "贪心" 从高到低。尽量先用最大的10，再尽量用次大的 5，.....

如果我们有无限数量面值为 1、5、11 的硬币，凑成 15 个硬币请问最少需要几个硬币？此次国家设计的硬币并没有按适合贪心的倍数规则来设计～

思考 2min...

依然用 "贪心"，15 = 11 + 1 + 1 + 1 + 1 这样的组合花费了 5 枚。

可是，15 = 5 + 5 + 5 这样的组合花费了 3 枚，显然这才是最优解。

emmm... 咋办？枚举找到 15 的所有硬币组合吧，可以使用回溯算法（dfs）。


#include<iostream>
#include<vector>
using namespace std;
 
int sum = 0;
vector<int> sum_arr;  // 存储当前sum值，是哪些数组成
int min_sum = 99999;  // 存储目标结果，硬币最少组合数
 
void dfs(vector<int>input, int n){
	if(sum == n){
		min_sum = min_sum > sum_arr.size()?sum_arr.size():min_sum;  // 更新最少组合数
	}
 
	if(sum > n)                          // 结束条件
		return;       
 
	for(int i=0; i<3; i++){              // 从选择列表里
		sum += input[i];                 // 做选择
		sum_arr.push_back(input[i]);     // 添加
		
		dfs(input, n);                   // 枚举下一个
		
		sum -= input[i];                 // 撤销当前选择
		sum_arr.pop_back();		         // 删除
	}
}
 
int main(){
	vector<int> input = {1, 5, 11};
	dfs(input, 15);
	cout << "硬币最少组合数：" << min_sum;  // 15 时，值为 3
}

但枚举时间复杂度太高，它把有用没用的信息都包含进去了。要提高算法效率，就少做无用功，我们只提取出有用的信息。

我们分析一下，15 这个数可以从哪里来？

因为我们只有 1、5、11 的面值，所以 15 只能从 3 种面值过来也就是 14:(15-1)、10:(15-5)、4:(15-11)。

我们再建立一个数学模型，凑成 n 需要最少的硬币数是 f(x)。

f(15) 可以写成
f(14) +1，+1 是取了面值为 1 的硬币，现在变成凑 14；
f(10) +1，+1 是取了面值为 5 的硬币，现在变成凑 10；
f(4) +1，+1 是取了面值为 11 的硬币，现在变成凑 4；

那么，f(15)的最优解即 f(15) = { min( f(14) , f(10) , f(4) ) + 1 }，那么我们知道了f(15)，可是不知道 f(14) , f(10) , f(4)。

那么，我们再分析 f(14) , f(10) , f(4) 从哪里来 ?

同理呀，这三个也都只能从 1、5、10 的面值取，所以一直分解即可。

动态规划算法如何设计？

分析这个求解过程，不难分析出设计 "动态规划" 的重点 :

步骤1: 设计状态

设计状态，把我们面临的局面记为 x(各种东西，不止于数值而是我们面临的情况)：

寻找变量，比如凑 15，我选一枚 11 的硬币，要凑的目标金额从 15 变成了 4
一个变量，状态通常是一维 dp[i]，俩个变量，状态通常是二维 dp[i][j]
必要时，可以增加状态的维度，引入更多的约束条件，使得状态定义满足无后向性要求，具体参考《动态规划二》01背包的状态设计

对于状态 x，在某个阶段把我们需要的答案记为 f(x) ：

硬币问题中，f(15)是凑 15 的硬币最少数量

步骤2: 设计状态转移方程

目标是f(T)，把所有的阶段组合起来求出来：

找出 f(x) 与哪些局面有关(记为p)，通过 f(p) 推出 f(T)，硬币问题中 f(T) = min( f(p) ) + 1
硬币问题中，求的 f(15)，从哪里来，到哪里去，求 f(15) 需要求 f(14)、f(10)、f(4)······

编程实现是从前往后推，得明确最简单的情况 base case：

硬币问题中，凑的数额为 0 时，f(0) = 0

再DP框架改动程序逻辑：


dp[0][...][...] = 0;                                       // base case 初始化
 
for 状态1 in 状态1的所有取值：                               // 一维状态
    for 状态2 in 状态2的所有取值：                           // 二维状态
        for ...                                            // 三维状态
            dp[状态1][状态2][...] = 计算(选择1，选择2...)    // 状态转移方程

实现硬币问题：


#include <iostream>
#include <algorithm>
using namespace std;
 
// 从三个数中选出最小值，俩个数中选最小值，CPP库会提供的
int min( int x, int y, int z ) { 
    return (x>y?y:x)>z?z:(x>y?y:x);
}
 
// 面值为 1  5  11 的硬币，凑成 nums 最少需要多少枚
void dynamic_programming( int nums ) {
	// 边界判断
	if ( nums <= 0 )
	     return;
	     
	int dp[1000];                          //  缓存已经计算的结果，避免重复计算
    memset( dp, 0x3f, 1000*sizeof(int));   //  初始化为 0x3f
    dp[0] = 0;                             //  明确最简单的情况，base case
	
	// 从哪里来，从 1 考虑到 nums 递推实现
	for( int i = 1; i <= nums; i ++ ) {
		if( i >= 11 )
		     dp[i] = min( dp[i-1]+1, dp[i-5]+1, dp[i-11]+1 );
		else if( i >= 5 )
		     dp[i] = min( dp[i-1]+1, dp[i-5]+1 );
		else    // ( i >= 1 )
		     dp[i] = dp[i-1]+1;
		 
		printf(" %-3d ， 最少需要 %-3d 枚硬币组成 \n", i, dp[i]);
	}
}
 
int main() {
    int nums;
    printf("enter :>   ");
    scanf("%d", &nums);
    
    dynamic_programming(nums);
    return 0;
}

较死板，只能针对已知硬币种类。只有改变硬币种类（如面值为1、5、11改成2、3、4），程序就需要大改。


// 硬币种类通用版本
void dynamic_programming( int nums ) {
 // 边界判断
 if ( nums <= 0 )
      return;
 
  int dp[1000];                          //  缓存已经计算的结果，避免重复计算
  memset( dp, 0x3f, 1000*sizeof(int));   //  初始化为 0x3f
  dp[0] = 0;                             //  明确最简单的情况，base case
     
 int coin[] = {1, 5, 11};
 for( int i = 1; i <= nums; i ++ ) {
     for( auto v : coin ) {
         if( i-v < 0 ) continue;         // 避免越界
         dp[i] = min(dp[i], dp[i-v]+1);
  }
  printf(" %-3d ， 最少需要 %-3d 枚硬币组成 \n", i, dp[i]);
 }
}

动态规划俩大性质

最优子结构：大问题的解来自小问题

动态规划俩个性质之一：最优子结构

我们建立的数学模型f(x) --> 凑成 n 需要最少的硬币数，其中 "最少" 即意味这最优哦～

f(15) 与 f(14) , f(10) , f(4) 有关，所以大问题的最优解可由小问题的最优解推出，这个性质叫 "最优子结构"。

这就好像我们从三筐苹果中选出每筐中当中最大的那个，得到三个苹果，然后再从中选出最大的，这三个苹果中最大的也是这三筐苹果中最大的。

无后效性：未来只与现在有关，与过去及过去的过去都无关

动态规划俩个性质之一：无后效性

未来只与现在有关，与过去以及过去的过去都无关...

e.g. f(15) 只与 f(14) , f(10) , f(4) 有关，而 f(14) , f(10) , f(4) 是如何算出来的又与f(y)相关我们并不在意，因为对我们并不影响，这个性质叫 "无后效性"。

设计状态的小技巧: 寻找变量

按照抽象规则把当前局面描述下来，关键在于寻找原问题和子问题之间会变化的量。

e.g. 硬币问题中的变量只有一个：硬币的数量是无限的，唯一的变量是目标金额。

原问题中目标金额 = 15 时，用 1、5、11 凑一次，子问题目标金额分别是 14、11、4，原问题和子问题间会变化的量。

设计状态转移方程小技巧：我从哪里来，我到哪里去

我从哪里来

e.g. f(15) 从 f(4)、f(10)、f(14) 而来。

我到哪里去

e.g. f(15) 到 f(16)、f(20)、f(26) 而去。

加深理解

DAG最短路径

问题描述：给定一个城市地图，所有道路都是单行道，而且不会构成环。每条道路都有过路费，问您从源点S 到目标点T 花费最少的路径是多少？

采用 "动态规划" ，请设计状态和状态转移方程。

思考 2min...

分析一下，接着按照上面的模板，设计 "动态规划" 算法。

步骤1: 设计状态f(x)

x 是面临的情况, 选择哪个城市
f(P) 是源点S到某城市P(任意城市)的最少费用
f(T) 是求出从城市S到城市T的最少费用

步骤2: 状态转移方程

最后阶段：f(x) = min{ f(C)+20, f(D)+10 }，我从哪里来。要达到城市T，要么从城市C，要么从城市D。
所有阶段的决策应该写为 : f(P) = min{ f(R)+W(R, P) }，W：R 到 P 的过路费。

最优子结构: 为了节俭的美德，我们一直选择过路费最少的城市走。对于任意城市P，我们只关心到P的最小费用即 f(P)，如此反复解决之后的问题...

无后效性：对于一个城市P(任意城市)，一旦 f(P) 确定以后就不关心怎么去的。

e.g. 最后一个阶段去目标点f(P)，我们只需要调用f(C)和f(D) 即只知道城市C是40，城市D是20 而具体C、D的路线是怎么走的我们并不关心~


int G[N][N], n; int f[N];
// 过路费，城市数、记录最少花费的城市
f[0]=0; 
// 明确最简单的情况 base case
 
for (int i=1; i<n; i++) 
    f[i]=INF; // 初始化为无穷大
 
/* 核心代码 */
for (int x=0; x<n; x++) 
    for (int i=0; i<n; i++)
        f[x] = min(f[x], f[i]+G[i][x]);   
 
for (int i=0; i<n; i++) 
        cout<<f[i]<<" ";

最长上升子序列

简称 LIS ，即给定一个长度为 n 的序列 A ，从 A 中抽取出一个子序列，这个子序列需要单调递增(重复算 1 个)。

e.g. A = 1, 5, 3, 4, 6, 9, 7, 8，最长上升自序列就是 1, 3, 4, 6, 7, 8。

采用 "动态规划" 的思想，先考虑俩个问题：

设计状态？
状态 x 的出处 ?

记 f(x) 为 $a_{x}$ 结尾的 LIS 长度，那么我们需要求解的最长上升子序列的状态转移方程是 max{ f(x) }。

举个例子：A = { 1、5、3、4、6 }

f(x) 代表 $a_{x}$ 结尾的 LIS 长度。

这里的最长即max，使满足 "动态规划" 的最优子结构性质。

当 A 有 1 个元素(元素: 1)，我们面临的情况 x = 1，即 f(1)。f(1)长度就是自己{1}，f(1) = 1。

当 A 有 2 个元素(元素: 1、5)，我们面临的情况 x = 2, 即 f(2)。第 2 个元素大于第 1 个元素{1、5}，所以 f(2) = f(1) + 1 ，f(2) = 2。

当 A 有 3 个元素(元素: 1、5、3)，我们面临的情况 x = 3，即 f(3)。第 3 个元素小于第 2 元素{1、3}，所以 f(3) = f(2)，f(3) = 2。

当 A 有 4 个元素(元素: 1、5、3、4)，我们面临的情况 x = 4，即f(4)。第 4 个元素大于第 3 个元素{1、3、4}，所以 f(4) = f(3) + 1，f(4) = 3。

当 A 有 5 个元素(元素: 1、5、3、4、6)，我们面临的情况 x = 5，即f(5)。第 5 个元素大于第 4 个元素{1、3、4、6}，所以 f(5) = f(4) + 1，f(5) = 4。

状态 x 设计完毕，现在必须考虑状态 x 是怎么推出来的？

数数时，如果数到n，那么必先数到 n-1。

状态 x 推导同，要推导出 x，必先推导到 x-1，不过在 LIS 问题中，还需要满足 x 大于 $A_{p}$ 。

那，考虑每一个比 x 小的 p(在x前面的数)：若 $A_{x} > A_{p}$ ，则 f(x) = f(p) + 1。

语义分析：在一个数列中，使 $A_{x}$ 始终接着 $A_{p}$ 的后面，定能构造一个以 $A_{x}$ 结尾的子序列，而TA的长度是以 $A_{p}$ 结尾的LIS子序列长度多 1。

举个例子，从最小的状态推过来~

f(1) = 1；因为 f(1) 没有来源 $A_{p}$ ，自己形成的LIS数列长度为 1。

f(2) = f(1)+1；有 2 种状态，第 1 种和 f(1) 没有来源 $A_{p}$ ，自己形成的LIS数列长度为 1；第 2 种 (5 > 1) 可接 $A_{1}$ 后面，再接自己LIS长度为 2。

f(3) = f(1)+1; 有 3 种状态，第 1 种以自己开头什么都不接，LIS长度为 1；第 2 种接在 f(1) 或 f(2) 后面，LIS长度为 2，第 3 种接在 f(1)且f(2)后面，不过(1 < 5 > 3) $A_{x = 3} < A_{p=2}$ ，因此不满足。

f(4) = f(3)+1; 有 4 种状态 ......

f(5) = f(4)+1; 有 5 种状态，以自己开头什么都不接，接 f(1)、f(2)、f(3)、f(4) 后面 ......

因此，我们初步设计的状态转移方程：

俩层 for 循环，时间复杂度是 $O(n^{2})$ 。


#include <stdio.h>
 
int max( int x, int y ) { return x > y ? x : y; }
 
int main( ) {
	int n;
	scanf("%3d", &n);
	int f[1000], a[1000];
	for( int i = 0; i < n; i ++ )
	    scanf("%d", &a[i]);
	   
	for( int i = 0; i < n; i ++ ) {
		f[ i ] = 1;                             // 假如不接任何在 Ap 后面，LIS长度就是自己
		for( int j = 0; j < i; j ++ )           // 考虑数列中在 x(i) 前面的那些数p(j)可不可以
		     if( a[ j ] < a[ i ] )              // 并且满足LIS问题的第二个条件Ax > Ap
		         f[ i ] = max(f[i], f[j]+1);    // 状态转移方程
		  
		printf("f[%d] = %d\n", i+1, f[ i ]);
	}
	
	return 0;
}

最长公共子序列

来自《算法导论》，也称为 LCS 问题，用于 DNA 上匹配基因相似度......

DNA序列类似计算机的底层的二进制： 0、1，DNA 由 4 进制字母表组成：{A、C、G、T}。

亲子关系是通过 DNA序列相似程度来确定，可以用：

相对熵
......

比如，X 的 DNA 序列： A C A G C

Y 的 DNA 序列： C T G A C

最长公共自序列：C G C，LCS长度：3， LCS长度越长越相似。

在一个数列中，子串是一组下标连续的序列，而子序列是一组下标连续或不连续的序列。

如果枚举 X(如果Y短即Y) 的 DNA 序列，时间复杂度是 $O(2^{A})$ 因为每个元素有俩种选择：是 or 不是。

设计状态和状态转移方程和 LIS 类似。

采用 "动态规划" 的思想，先考虑俩个问题：

设计状态？
状态 x 的出处 ?

记 f(x) 为 LCS 长度，那么我们需要求解的最长公共子序列的状态转移方程是 max{ f(x) }。

状态 x 从哪里来？

$X_{m-1}$	$X_{m}$
$Y_{n-1}$	$Y_{n}$

要到 $X_{m}$ 、 $Y_{n}$ ，必先经过前缀 $X_{m-1}$ 和 $Y_{n-1}$ ，假设状态x 是一个序列 Z，也就是 X、Y 的最长公共子序列， $Z_{x-1} = X_{m-1} = Y_{n-1}$ 。

因为LCS序列Z 铁定从 $X_{m-1}$ 和 $Y_{n-1}$ 而来，如果 $X_{m}$ 和 $Y_{n}$ 相等，则 $Z_{x} = X_{m} = Y_{n}$ ，状态转移方程：max{ f(x-1)+1 };

若 $X_{n} \neq Y_{m}$ ，则 $Z_{x} = X_{m}$ 或 $Z_{x} = Y_{n}$ ，LCS长度保持不变，状态转移方程：max{ f(X)，f(Y) }。

建立一个二维数组 f[m][n] 存储 LCS长度，满足无后效性(记忆化搜索)。

因此，所有情况的状态转移方程：

f[i][j] = {

0 (i=0，j=0);

f[i-1][j-1]+1 (i>0，j>0，x[i]=y[j]);

max{ f[i][j-1]，f[i-1][j] } (i>0,j>0, max(x[i]，y[j]) 比较 $X_{m}$ 和 $Y_{n-1}$ 与 $X_{m-1}$ 和 $Y_{n}$ );

}


#include<string.h>
#include<stdlib.h>
int max( int x, int y ) { return x > y ? x : y; }
char Lcs[1024];    // 存储最长公共子序列
 
int lcs(char *X, char *Y)
{
	int m = strlen(X);
	int n = strlen(Y);
	int L[m + 1][n + 1];
 
	for (int i = 0; i <= m; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			if (i == 0 || j == 0)
				L[i][j] = 0;
			else if (X[i - 1] == Y[j - 1])
				L[i][j] = L[i - 1][j - 1] + 1;
			else
				L[i][j] = max(L[i - 1][j], L[i][j - 1]);
		}
	}
 
	int index = L[m][n];
	Lcs[index] = '\0';    // 在末尾填 \0，方便输出		
 
	int i = m, j = n;
	while (i > 0 && j > 0)
	{
		if (X[i - 1] == Y[j - 1])
			Lcs[index - 1] = X[i - 1],
			i--, j--, index--;	
		else
                        L[i - 1][j] > L[i][j - 1] ? i-- : j--;		
	}
    return L[m][n];    // 返回LCS长度, 中文可能不准确
}
 
int main()
{
	char X[] = "https://mp.csdn.net/postedit/89306524";
	char Y[] = "https://blog.csdn.net/qq_41739364";
 
	printf("LCS : [%d] \n lcs:> %s\n", lcs(X, Y), Lcs);
}

LIS、LCS 问题：优化策略

最大子段和

问题描述：给出一个整数数列，求最大子段和。

e.g. [2, -1, 3, -5, 3] 的最大子段和是 2 + (- 1) + 3 = 4。

采用 "动态规划" 的思想，先考虑俩个问题：

设计状态？
状态 x 的出处 ?

解 1：以 dp[x] 表示 [0, x] 位的最大子段和，以 a[x] 结尾。

解 2: 状态 x ，一般情况是从 x-1 而来即，dp[x-1]，特殊一点是从自己开始。

推出状态转移方程：dp[x] = max(dp[x-1] + a[x]，a[x]);

方程表达意思： dp[x-1] + a[x]: 当前x(即a[x])合并之前的最大子段和(即dp[x-1])，a[x]直接从自己开始。


#include <stdio.h>
int dp[1024], a[1024];
 
int max(int x, int y) { return x > y ? x : y; }
 
int main() {
	int n;
	scanf("%3d", &n);                           // 防止溢出
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
 
	for (int i = 0; i < n; i++) {               // i 就是设计状态 x
		dp[i] = max(dp[i - 1] + a[i], a[i]);    // 状态转移方程
		printf("dp[%d] = %d\n", i+1, dp[i]);
	}
}

上楼梯

问题描述：楼梯有 n 阶，上楼可一步上 1 阶，也可以一步上 2 阶，能计算出共有多少种走法吗？

采用 "动态规划" 的思想，先考虑俩个问题：

设计状态？
状态 x 的出处 ?

解 1: 记走 x 阶的方案数为 f(x)，n 阶就是f(n)。

解 2: 状态 x，只有俩种走法。因此，要么从 x-1，要么从 x-2 。

现在假设状态 x = 7，

差一阶：1 到 6 阶走法有 a 种，

差俩阶：1 到 5 阶走法有 b 种，

要么从 6 阶走上去，要么从 5 阶走上去，所以走上 7 阶共 a + b 种方法。

状态转移方程: f(x) = f(x-1) + f(x-2)

发现就是一个 fib 数列，可以采用优化矩阵快速幂......


#include <stdio.h>
 
int main( ) {
    int n;
    scanf("%d", &n);
	
    int f[1024] = { 0 };               // 定义状态
    // 初始化边界值
    f[1] = 1;
    f[2] = 2;
    
    for( int i = 2; i <= n; i++ ) 
        f[i] = f[i - 1] + f[i - 2];    // 状态转移方程
    
    
    for( int i = 1; i <= n; i ++ )
        printf("f[%d] = %d\n", i, f[i]);
}

DP经验

怎么确认问题能不能采用 "动态规划" 的思想解决？

第一反应，直觉。如果您觉得这道题可以 DP，那么开始考虑设计状态x。
第二反应，性质。设计的 x 是否满足最优子结构、无后效性，若都满足，进入下一步。
第三反应，经验。设计状态转移方程，如果可以设计出来，就可以用 DP。

怎么设计状态？

想办法把当前局面表示出来。

怎么设计状态转移方程？

从哪里来
到哪里去

"动态规划" 是一种思想，用递归和递推实现这个思想都是 "动态规划"。

学习 DP 的阶段指南？

初学阶段，最难的地方 --设计状态(小白找不着好转移的状态)
小成阶段，最难的地方 --设计状态转移方程(遇到各种各样的优化：数据结构、算法优化如二分)
大白阶段，最难的地方 --设计状态(掌握后许多优化技巧，又发现设计状态难因为一个问题也许可以设计出许多种DP算法，每个算法信息量不一样，因此各种 DP 复杂度不一样)

DP应用

DP应用一：论文查重，这很简单。

即 LCS 问题，最长公共子序列，看看上文自此第一个目标实现。

或者使用余弦定理判断：计算机新闻分类

DP应用二：拼写纠错，开放式问题。

这里说的是英文单词拼写纠错，既然是纠错肯定得先知道单词是否拼错。

所以呀，纠错之前需要判断单词是否错误。

我们可以在计算机里建立一个词库，把英文词典的单词都包含着。

不过，这个词库该怎么设计才能高效查询呢？

常规方法应该是，按照单词的字典序排序再用二分查找判断一个单词是否正确。

一般英文词典单词数量大概是 24万 - 25万，二分只需要对比 17 - 18 次。

又因为英文单词的平均长度是 6 个字母，对比一个单词需要 6 次，一共大概是 102 - 108 次。

说到存储和查询，很容易想起一种哈希表和哈希查找......

采用哈希表存储单词，大概只需要对比 2 次。

又因为英文单词的平均长度是 6 个字母，对比一个单词需要 6 次，一共大概是 12 次。

词典在存储时(环境是手机)，可以采用 "布隆过滤器" 压缩存储。

假设我们已经设计好了词库，现在如何判断单词是否正确拼写？

比如，华盛顿的英文: Washington，

而我们敲的: Wasingdon。

字母 s 和字母 i 之间少了一个 h，后面的字母 t 写成字母d。

如果采用最邻近的方法，一一对比：

正确拼写(华盛顿)	W	a	s	h	i	n	g	t	o	n
错误拼写	W	a	s	i	n	g	d	o	n	\

错了 7 个，如果词典里还有一个相似的单词呢而且错误数更少但不是我们想要的内容？

比如，另外一个英国人的名字 Watingdon，

错误拼写	W	a	s	i	n	g	d	o	n
华盛顿	W	a	s	h	i	n	g	t	o	n
另外的人名	W	a	t	i	n	g	d	o	n

显然，如果采用最邻近算法计算机会选错因为，华盛顿错了 7 个，而另外的人名只错 1 个。

这里，您肯定会觉得干嘛要一一对比呢，s 和 i 之间没加 h 应该补一个字母或加一个占位字母，这样就拼写华盛顿就只错俩个。

正确拼写	W	a	s	h	i	n	g	t	o	n
错误拼写	W	a	s	\	i	n	g	d	o	n

那么现在的问题清晰了，如何让计算机明白什么时候补占位字母呢？

在构词学中，单词间差异程度叫 "编辑距离"。

百度一下，DP解编辑距离发现资料一大堆......

e.g. 字符串相似度算法（编辑距离算法 Levenshtein Distance） - ZYB - 博客园

看一下资料，最短编辑距离是这样：

把编辑距离小于某个设定数，列为备选。

最后，如同机器学习一样按照出现概率选择显然华盛顿出现的概率远大于普通人的名字。

但更好的是更据上下文推断到底是哪个名字，可采用 "维比特算法" 实现。

到这，第二个目标实现。

再回到第一步，如何判断单词是否错误。

我们说了俩种方法存储词典：排序+二分、哈希表+哈希查找。

其实这俩种都挺好，不过您想一想我们敲代码的时候只需要输前几个字母，完整的单词就自动出现了。

我们得设计这种啊，省时省力......

这种设计方法，来源于一种数据结构：二叉树。

我曾在《密码学》写过二叉数加密，这里也类似不过是分支多点。

一颗二叉树，每个结点都可以有俩个子结点。

只需要俩个即可，因为一直分下去，分支就呈指数叠加这让俩个子结点就等同任意子结点。

设计的二叉树词典，每个结点需要 26 个分支代表 26 个字母。(分支不超过256，计算机实现就不困难)

当输入完 W、a、s，26 叉树也在跟着走(可显示出)，再输入 i 6这时假设没有单词可匹配，26 叉树就不会出现提示用户就知道拼写错了。

采用 26 叉树的查找完全是用户输入时的字母对应的子结点，只需要对比一次即可，而英文单词平均长度是 6，即判断一个单词是否错误只需要 6 次。

最主要的是，实现了代码提示器再设计一番还可以偷懒。

DP应用三：假设算法服务对象是汽车。

车载地图的算法需要考虑到汽车是不断移动，结果会不断更新。

发现这是一个多阶段决策问题，而且满足 "动态规划" 的最优子结构性质。

现在回想这个不就类似上面学的最短路径(正常情况距离不可能为负，无负权边)吗？

我们需要搞清楚每个加油站位置和汽车现在的位置，以及行车方向。

距离计算，从汽车的位置到最近的加油站可能会经过许多直线距离片段的叠加。

路径的组合可能有成千上万种，我们需要最短的一条。

"动态规划" 的另一条性质是无后效性，我们可以提前计算出所有路口的距离。

我们当然可以动态规划算法时实时计算，但地图这几年内基本不会变。

当汽车在某个位置寻找加油站时，只需要算一下汽车当前位置到附近几个近的路段，再计算一下加油站到这几个路段的距离。

因为已经计算好了，所以只需要相加即可。

也可以使用快排(堆排会更快)，不过效率都比不上采用 "动态规划" 的算法。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/837024

动态规划一：动态规划算法如何设计_写出设计动态规划算法的主要步骤。

历史

初探

动态规划算法如何设计 ？

动态规划俩大性质

最优子结构：大问题的解来自小问题

无后效性：未来只与现在有关，与过去及过去的过去都无关

设计状态的小技巧: 寻找变量

设计状态转移方程小技巧：我从哪里来，我到哪里去

加深理解

DAG最短路径

最长上升子序列

最长公共子序列

最大子段和

上楼梯

DP经验

DP应用

动态规划算法如何设计？