动态规划算法

Post author:xfxia
Post published:2023年7月22日
Post category:其他

动态规划算法

动态规划（Dynamic programming）

是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。关于动态规划最经典的问题当属背包问题（不探讨）。

动态规划算法特性

最优子结构性质：

如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

子问题重叠性质：

子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

无后效性：

即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

解题思路：

1、

划分：

按照问题的特征，把问题分为若干阶段。注意：划分后的阶段一定是有序的或者可排序的
2、

确定状态和状态变量：

将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性
3、

确定决策并写出状态转移方程：

状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程
4、

边界条件：

状态转移方程是一个递推式，因此需要找到递推终止的条件

即：

【初始状态】→【决策1】→【决策2】→…→【决策n】→【结束状态】

注意：

问题阶段

每个阶段的状态

相邻两个阶段之间的递归关系

以上便是动态规划的基础理论，下面借助 LeetCode 的一道题目来加深理解

题目

题目：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符

‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

示例 1：

输入：s = “aa” p = “a”

输出：false

解释：“a” 无法匹配 “aa” 整个字符串。

示例 2：

输入：s = “aa” p = “a*”

输出：true

解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

来源：

力扣（LeetCode）

LeetCode 官方解题思路

题目中的匹配是一个「逐步匹配」的过程：我们每次从字符串

p

$p$

中取出一个字符或者「字符 + 星号」的组合，并在

s

$s$

中进行匹配。对于

p

$p$

中一个字符而言，它只能在

s

$s$

中匹配一个字符，匹配的方法具有唯一性；而对于

p

$p$

中字符 + 星号的组合而言，它可以在

s

$s$

中匹配任意自然数个字符，并不具有唯一性。因此我们可以考虑使用动态规划，对匹配的方案进行枚举。

我们用

[

i

]

[

j

]

f[i][j]

$f [i] [j]$

表示

s

$s$

的前

i

$i$

个字符与

p

$p$

中的前

j

$j$

个字符是否能够匹配。在进行状态转移时，我们考虑

p

$p$

的第

j

$j$

个字符的匹配情况：

如果

p

$p$

的第

j

$j$

个字符是一个小写字母，那么我们必须在

s

$s$

中匹配一个相同的小写字母，即

[

i

]

[

j

]

=

{

f

[

i

−

1

]

[

j

−

1

]

,

s

[

i

]

=

p

[

j

]

f

a

l

s

e

,

s

[

i

]

≠

p

[

j

]

f[i][j]= \begin{cases} f[i−1][j−1],\,\,\,\ s[i]=p[j]\\ false,\,\,\, \, \, \, \, \, \, \,\, \, \, \,\, \, \, \, \, \ s[i] \neq p[j]\\ \end{cases}

$f [i] [j] = {f [i - 1] [j - 1], s [i] = p [j] f a l s e, s [i] \neq = p [j]$

也就是说，如果

s

$s$

的第

i

$i$

个字符与

p

$p$

的第

j

$j$

个字符不相同，那么无法进行匹配；否则我们可以匹配两个字符串的最后一个字符，完整的匹配结果取决于两个字符串前面的部分。

如果

p

$p$

的第

j

$j$

个字符是
*
，那么就表示我们可以对

p

$p$

的第

−

1

j-1

$j - 1$

个字符匹配任意自然数次。在匹配 0 次的情况下，我们有

[

i

]

[

j

]

=

f

[

i

]

[

j

−

2

]

f[i][j]=f[i][j−2]

$f [i] [j] = f [i] [j - 2]$

也就是我们「浪费」了一个字符 + 星号的组合，没有匹配任何

s

$s$

中的字符。

在匹配

,

2

,

3

,

⋯

1,2,3, \cdots

$1, 2, 3, \dots$

次的情况下，类似地我们有

[

i

]

[

j

]

=

f

[

i

−

1

]

[

j

−

2

]

,

if

s

[

i

]

=

p

[

j

−

1

]

f

[

i

]

[

j

]

=

f

[

i

−

2

]

[

j

−

2

]

,

if

s

[

i

−

1

]

=

s

[

i

]

=

p

[

j

−

1

]

f

[

i

]

[

j

]

=

f

[

i

−

3

]

[

j

−

2

]

,

if

s

[

i

−

2

]

=

s

[

i

−

1

]

=

s

[

i

]

=

p

[

j

−

1

]

⋯

⋯

\begin{aligned} & f[i][j] = f[i – 1][j – 2], \quad && \text{if~} s[i] = p[j – 1] \\ & f[i][j] = f[i – 2][j – 2], \quad && \text{if~} s[i – 1] = s[i] = p[j – 1] \\ & f[i][j] = f[i – 3][j – 2], \quad && \text{if~} s[i – 2] = s[i – 1] = s[i] = p[j – 1] \\ & \cdots\cdots & \end{aligned}

$f [i] [j] = f [i - 1] [j - 2], f [i] [j] = f [i - 2] [j - 2], f [i] [j] = f [i - 3] [j - 2], \dots \dots if s [i] = p [j - 1] if s [i - 1] = s [i] = p [j - 1] if s [i - 2] = s [i - 1] = s [i] = p [j - 1] $

如果我们通过这种方法进行转移，那么我们就需要枚举这个组合到底匹配了

s

$s$

中的几个字符，会增导致时间复杂度增加，并且代码编写起来十分麻烦。我们不妨换个角度考虑这个问题：字母 + 星号的组合在匹配的过程中，本质上只会有两种情况：

匹配

不匹配字符，将该组合扔掉，不再进行匹配。

如果按照这个角度进行思考，我们可以写出很精巧的状态转移方程：

[

i

]

[

j

]

=

{

f

[

i

−

1

]

[

j

−

1

]

o

r

f

[

i

]

[

j

−

2

]

,

s

[

i

]

=

p

[

j

−

1

]

f

[

i

]

[

j

−

2

]

,

s

[

i

]

≠

p

[

j

−

1

]

f[i][j]= \begin{cases} f[i−1][j−1] \ or \ f[i][j−2],\,\ s[i]=p[j-1]\\ f[i][j−2],\,\,\, \,\, \, \, \,\,\,\, \,\, \, \, \,\,\,\, \,\, \, \, \,\,\, \, \,\, \, \, \,\,\,\, \,\, \, \, \,\,\ s[i] \neq p[j-1]\\ \end{cases}

$f [i] [j] = {f [i - 1] [j - 1] o r f [i] [j - 2], s [i] = p [j - 1] f [i] [j - 2], s [i] \neq = p [j - 1]$

在任意情况下，只要

[

j

]

p[j]

$p [j]$

是 .，那么

[

j

]

p[j]

$p [j]$

一定成功匹配

s

$s$

中的任意一个小写字母。

最终的状态转移方程如下：

[

i

]

[

j

]

=

{

i

f

(

p

[

j

]

)

≠

‘

∗

’

)

=

{

f

[

i

−

1

]

[

j

−

1

]

,

m

a

t

c

h

e

s

(

s

[

i

]

,

p

[

j

]

)

f

a

l

s

e

,

o

t

h

e

r

w

i

s

e

o

t

h

e

r

w

i

s

e

=

{

f

[

i

−

1

]

[

j

]

o

r

f

[

i

]

[

j

−

2

]

,

m

a

t

c

h

e

s

(

s

[

i

]

,

p

[

j

−

1

]

)

f

[

i

]

[

j

−

2

]

,

o

t

h

e

r

w

i

s

e

f[i][j]= \begin{cases} if(p[j]) \neq ‘*’)= \begin{cases} f[i−1][j−1],\,\,\,\, matches(s[i],p[j]) \\ false, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, otherwise \end{cases}\\ otherwise= \begin{cases} f[i−1][j] \ or \ f[i][j−2],\,\,\, matches(s[i],p[j-1]) \\ f[i][j−2], \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\ otherwise \end{cases} \\ \end{cases}

$f [i] [j] = ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎧ i f (p [j]) \neq = ‘ * ’) = {f [i - 1] [j - 1], m a t c h e s (s [i], p [j]) f a l s e, o t h e r w i s e o t h e r w i s e = {f [i - 1] [j] o r f [i] [j - 2], m a t c h e s (s [i], p [j - 1]) f [i] [j - 2], o t h e r w i s e$

其中

(

x

,

y

)

\textit{matches}(x, y)

$matches (x, y)$

判断两个字符是否匹配的辅助函数。只有当

y

$y$

是
.
或者

x

$x$

和

y

$y$

本身相同时，这两个字符才会匹配。

动态规划的边界条件为

[

0

]

[

0

]

=

true

f[0][0] = \text{true}

$f [0] [0] = true$

，即两个空字符串是可以匹配的。最终的答案即为

[

m

]

[

n

]

f[m][n]

$f [m] [n]$

，其中

m

$m$

和

n

$n$

分别是字符串

s

$s$

和

p

$p$

的长度。由于大部分语言中，字符串的字符下标是从

0

$0$

开始的，因此在实现上面的状态转移方程时，需要注意状态中每一维下标与实际字符下标的对应关系。

在上面的状态转移方程中，如果字符串

p

$p$

中包含一个「字符 + 星号」的组合（例如
a*
），那么在进行状态转移时，会先将
a
进行匹配（当

[

j

]

p[j]

$p [j]$

为
a
时），再将
a*
作为整体进行匹配（当

[

j

]

p[j]

$p [j]$

为
*
时）。然而，在题目描述中，我们必须将
a*
看成一个整体，因此将
a
进行匹配是不符合题目要求的。

示例代码 C# 版

注意：

C# 声明二维数组的方式
C# 中没有
CharAt()
方法可以使用
Convert.ToChar(p.Substring(int, int))
来替代

从此实例检索子字符串。子字符串从指定的字符位置开始且具有指定的长度。即参数一：起始位；参数二：子串长度

public static bool IsMatch(string s, string p)
{
    int m = s.Length;
    int n = p.Length;

    bool[,] f = new bool[m + 1, n + 1];
    f[0, 0] = true;
    for (int i = 0; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (Convert.ToChar(p.Substring(j - 1, 1)) is '*')
            {
                f[i, j] = f[i, j - 2];

                if (Matches(s, p, i, j - 1)) f[i, j] = f[i, j] || f[i - 1, j];
            }
            else
            {
                if (Matches(s, p, i, j)) f[i, j] = f[i - 1, j - 1];
            }
        }
    }
    return f[m, n];
}

public static bool Matches(string s, string p, int i, int j)
{
    if (i is 0) return false;

    if (Convert.ToChar(p.Substring(j - 1, 1)) is '.') return true;

    return Convert.ToChar(s.Substring(i - 1, 1)) == Convert.ToChar(p.Substring(j - 1, 1));
}

最后想和小伙伴们说动态规划比较晦涩难懂，还需慢慢体悟。只此一篇论述浅薄，有心之人可自行查找相关资料进行学习。

版权声明：本文为qq_43562262原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/qq_43562262/article/details/121248980