【从零开始的动态规划02】——双串问题dp[i][j]，矩阵DP，无串线性DP

导语

上一篇文章【从零开始的动态规划01】——单串问题dp[i]中，我们介绍了动态规划的定义，特征，和常见单串问题的总结。本篇我们将聚焦双串问题dp[i][j]。

什么是双串问题？

单串问题的输入为一个串，且每个子问题只与位置i有关（有时可能会添加一些指标k，变成dp[i][k]，但位置终究是i），而双串问题的输入为两个串，长度分别为m和n，子问题需要用i和j两个变量表示，分别代表第一个串和第二个串考虑的位置dp[i][j]:=第一串考虑[0…i]，第二串考虑[0…j]时原问题的解。

拆解较大规模的子问题时，可以拆解成i规模更小，j规模更小，或者i和j规模都减小的子问题，即dp[i][j]通常与dp[i-1][j], dp[i][j-1], dp[i-1][j-1]有关。

---

A. 最长公共子序列（经典LCS系列，i, j非必须取）

练习题1：LeetCode 1143. 最长公共子序列

题目大意：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

状态定义：设dp[i][j]表示text1第i个字符为末尾的字符串与text2第j个字符为末尾的字符串的最长公共子序列长度

初始状态：每个元素在没有和别的元素进行匹配的时候，公共部分为0。因此，dp[i][j]初始等于0

状态转移：对于i和j，如果text1[i-1]=text2[j-1]，那么以i和j为末尾的字符串的公共子序列长度为：分别排除i和j的剩下的部分的公共子序列长度+1；如果text1[i-1] != text2[j-1]，那么我们只能保留公共子序列长度最长的那部分，这个部分来自于dp[i-1][j]或者dp[i][j-1]。得到状态转移方程：
$$dp[i][j]=\{\begin{array}{r}max(dp[i][j-1],dp[i-1][j]),text1[i]!=text2[j]\\ dp[i-1][j-1]+1,text1[i]=text2[j]\end{array}$$

练习题2：LeetCode 712. 最长公共子序列

题目大意：给定两个字符串 s1 和 s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。

状态定义：设dp[i][j]表示text1第i个字符为末尾的字符串与text2第j个字符为末尾的字符串的最长公共子序列的ASCII最大和

初始状态：每个元素在没有和别的元素进行匹配的时候，公共部分为0。因此，dp[i][j]初始等于0

状态转移：题目要求使两者字符串相同所需要删除的字符的最小和，那么我们只要求出最长公共子序列的最大ASCII和，用总和减去这个和，就能得到删除字符的最小和。

对于i和j，如果s1[i-1]=s2[j-1]，那么以i和j为末尾的字符串的公共子序列长度为：分别排除i和j的剩下的部分的公共子序列的ASCII最大和+s1[i]*2；如果s1[i-1] != s2[j-1]，那么我们只能保留公共子序列ASCII和最大的那部分，这个部分来自于dp[i-1][j]或者dp[i][j-1]。得到状态转移方程：
$$dp[i][j]=\{\begin{array}{r}max(dp[i][j-1],dp[i-1][j]),s1[i-1]!=s2[j-1]\\ dp[i-1][j-1]+s1[i]\times 2,s1[i-1]=s2[j-1]\end{array}$$

练习题3：LeetCode 718. 最长重复子数组

题目大意：给定两个整数数组A和B，返回这两个数组中公共的，长度最长的子数组的长度。

状态定义：设dp[i][j]表示A的第i个元素为末尾的子数组与B的第j个元素为末尾的子数组的最长公共子数组最大长度。

初始状态：每个元素在没有和别的元素进行匹配的时候，公共部分为0。因此，dp[i][j]初始等于0

状态转移：对于i和j，如果A[i-1]=B[j-1]，那么以i和j为末尾的子数组的公共子序列长度为：分别排除i和j的剩下的部分的公共子序列长度+1；如果A[i-1] != A[j-1]，那么我们只能保留公共子序列长度最长的那部分，这个部分来自于dp[i-1][j]或者dp[i][j-1]。得到状态转移方程：
$$dp[i][j]=\{\begin{array}{r}max(dp[i][j-1],dp[i-1][j]),A[i]!=B[j]\\ dp[i-1][j-1]+1,A[i]=B[j]\end{array}$$

B. 字符串匹配

练习题1：LeetCode 72. 编辑距离

题目大意：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。可以进行三种操作，插入一个字符，删除一个字符，替换一个字符。

状态定义：设dp[i][j]表示word1第i个字符为末尾的字符串修改成word2第j个字符为末尾的字符串的最小操作次数

初始状态：每个元素在没有和别的元素进行匹配的时候，修改次数为0。因此，dp[i][j]初始等于0。dp[0][j]表示将空串修改成word2以第j个字符为末尾的字符串需要的最小操作数，dp[0][j]=j。同样的，dp[i][0]表示将word1以第i个字符为末尾的字符串修改成空串的最小操作数,dp[i][0]=i。

状态转移：对于i和j，如果word1[i-1]=word2[j-1]，那么i和j不需要修改，两个字符串的最小修改次数应和排除i和j，剩余的部分的最小修改数相同，即dp[i][j]=dp[i-1][j-1]。如果word1[i-1]!=word2[j-1]，那么我们只能从三种操作里选择一个操作次数最小的，然后+1（修改i和j中的一个）。得到状态转移方程：
$$dp[i][j]=\{\begin{array}{r}min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1,text1[i]!=text2[j]\\ dp[i-1][j-1],text1[i]=text2[j]\end{array}$$

练习题2：LeetCode 44. 通配符匹配

题目大意：给定一个字符串(s) 和 一个字符模式§, 实现一个支持‘?’和’*'的通配符匹配。?可以匹配任何单个字符；*可以匹配任何字符串（包括空字符串）。两个字符串完全匹配才能算匹配成功。

状态定义：设dp[i][j]表示s的第i个字符为末尾的字符串与p的第j个字符为末尾的字符串是否匹配。

初始状态：dp[0][0]表示空串与空串匹配，必定为true。遍历p数组，如果p[i-1]为*，则dp[0][i]=true, 否则退出遍历。

状态转移：对于i和j，如果s[i-1]=p[j-1]或者p[j-1]=?，那么i和j匹配成功，而以i和j为末尾的两个字符串是否匹配，取决于排除i和j之后剩余的部分能否匹配，因此dp[i][j]=dp[i-1][j-1]。如果s[i-1]!=p[j-1]且p[j-1]=*，那么有两种操作：使用*和不使用*。如果使用
*，则只需要匹配i-1个字符，dp[i][j]=dp[i-1][j], 如果不使用，则p少了一个*字符，dp[i][j]=dp[i][j-1]
得到状态转移方程：
$$dp[i][j]=\{\begin{array}{r}dp[i-1][j-1],s[i-1]=p[j-1]\vee p[j-1]=?\\ dp[i-1][j]\vee dp[i][j-1],s[i-1]!=p[j-1]\wedge p[j-1]=\ast \end{array}$$

练习题3：LeetCode 44. 正则表达式匹配

题目大意：给定一个字符串(s) 和 一个字符模式§, 实现一个支持‘.’和’*‘的通配符匹配。’.‘可以匹配任何单个字符；’*'可以匹配任何字符串（包括空字符串）。两个字符串完全匹配才能算匹配成功。

状态定义：设dp[i][j]表示s的第i个字符为末尾的字符串与p的第j个字符为末尾的字符串是否匹配。

初始状态：为了考虑空字符串匹配的情况，我们将数组向右移动了一位，此时，我们需要遍历p，初始化dp，因为星号*前面必有别的字符，因此我们从j=2开始遍历，即p[j-1]==星号，且前面dp[0][j-2]是匹配的，则dp[0][j]也是匹配的。

状态转移：当p为星号时，它可以删除前一个字符或增加前一个字符，因此，有三种情况可以匹配:

(1) 删除前一个字符：那么就需要向前两位的字符之前的字符串是否匹配,即dp[i][j-2]=true时，dp[i][j]也等于true，因为需要考虑空字符串的状态，因此我们将整个数组右移一位，dp[i][j]指向的是s[i-1]和p[j-1]的匹配情况，而dp[i][j-2]指向的是s[i-1]和p[j-3]的匹配情况，即删除了j-2（星号前面的字符）和j-1（星号）后能否匹配

(2)添加一个前面的字符：假如s[i-1]和p[j-2]（星号前面的字符匹配），且在不添加这个字符之前，s[i-2]和p[j-1]是匹配的，那么添加这个字符后，s[i-1]和p[j-1]也能匹配，即
dp[i-1][j]&&s[i-1]==p[j-2] 为真时，dp[i][j]=true

(3)添加一个万用符：假如p[j-2]为点号，那么相当于添加了一个万用符，只要不添加之前s[i-2]与p[j-1]是匹配的，那么添加字符后也是匹配的

当p不为星号时，有两种情况可以匹配：
(1) s[i-1]和p[j-1]之前都是匹配的且s[i-1]==p[j-1]，那么可以匹配
(2) s[i-1]和p[j-1]之前都是匹配的且p[j-1]为点号，那么可以匹配

得到状态转移方程：

$$dp[i][j]=true\{\begin{array}{r}p[j-1]=\ast \wedge s[i-1]=p[j-2]\wedge dp[i-1][j]--s[i-1]与\ast 号前的字符匹配\\ p[j-1]=\ast \wedge p[j-2]=.\wedge dp[i-1][j]--\ast 号前的字符为万能符\\ dp[i][j-2]--删除\ast 号和之前的字符\\ s[i-1]=p[j-1]\wedge dp[i-1][j-1]--s[i-1]与p[j-1]匹配\\ p[j-1]=.\wedge dp[i-1][j-1]--p[j-1]是万能符\end{array}$$

C. 其他双串问题

练习题1：LeetCode 97. 交错字符串

题目大意：给定三个字符串s1，s2，s3，请你帮忙验证s3是否是由s1和s2交错组成的。两个字符串s和t交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：

1. s=s1+s2+…+sm
2. t=t1+t2+…+tn
3. |m-n|<=1
4. 交错是s1+t1+s2+t2+s3+t3+…或者t1+s1+t2+s2+t3+s3+…

状态定义：设dp[i][j]表示s1的第i个字符为末尾的字符串与s2的第j个字符为末尾的字符串是否交错匹配s3的第i+j字符为末尾字符串

初始状态：为了考虑空字符串匹配的情况，我们将数组向右移动了一位。dp[0][0]表示空字符串与空字符串的匹配，必定为true

状态转移：如果s1的第i个字符与s3第i+j个字符匹配，则i串和j串能否交错匹配s3的i+j-1部分，依赖于i-1串和j串能否交错匹配s3的i+j-1部分。类似的，如果s2的第j个字符与s3第i+j个字符匹配，dp[i][j] = s3[i+j-1]==s2[j-1] && dp[i][j-1]。因此：
$$dp[i][j]=trueif:\{\begin{array}{r}s3[i+j-1]=s1[i-1]且dp[i-1][j]\\ s3[i+j-1]=s2[j-1]且dp[i][j-1]\end{array}$$

练习题2：LeetCode 115. 不同的子序列

题目大意：给定一个字符串s和一个字符串t，计算在s的子序列中t出现的个数。

状态定义：设dp[i][j]表示s的第i个字符为末尾的字符串中出现t的第j个字符为末尾的字符串的个数

初始状态：为了考虑空字符串匹配的情况，我们将数组向右移动了一位。当j=0时，表示为空字符串，而空字符串是任何字符串的子序列，因此dp[i][0]=1

状态转移：如果s[i-1]==t[j-1]，那么有两种选择，使用s[i-1]去匹配t[j-1]，那么出现t[:j]的个数依赖于t[:j-1]出现在s[:i-1]的次数，dp[i][j] = dp[i-1][j-1]；如果不使用s[i-1]，那么出现t[:j]的个数依赖于t[:j]出现在s[:i]的次数，故:dp[i]/[j] = dp[i-1]/[j]。如果s[i-1]!=t[j-1]，那么只能不使用s[i-1]去匹配t[:j]，dp[i][j]=dp[i-1][j]。得到状态转移方程：
$$dp[i][j]=\{\begin{array}{r}dp[i-1][j-1]+dp[i-1][j]，s[i-1]=t[j-1]\\ dp[i-1][j]，s[i-1]\ne t[j-1]\end{array}$$

练习题3：LeetCode 87. 扰乱字符串

题目大意：给定一个字符串s和t，可以对s进行下面的操作：

1. 当字符串长度为1，则停止操作
2. 随机选择s中的一个位置i，将s分割成两部分l1和r1，有两种选择，交换或者不交换。如果交换，则s=r1+l1；如果不交换，则s=l1+r1
3. 拆分之后，可以分别对l1和r1执行上面的操作。
   问，能否通过操作使得s变成t。

状态定义：设dp[i][j][k]表示s的第i个字符开始，长度为k的字符串中出现t的第j个字符开始，长度为k的字符串是否为扰乱字符串。

初始状态：初始没有进行比对，均为非扰乱字符串，dp[i][j][k]=false。而当长度为1，且s[i]==t[i]时，彼此一定是对方的扰乱字符串，因此 dp[i][j][1]=true

状态转移：从len=2开始枚举长度至n，从i=0开始枚举s串的起点，从j=0开始枚举t串的起点，从k=1开始枚举子串长度，进行”分割“（实际并不会分割），对于分割后的子串，有两种选择：不交换，交换。设s串分割后得到l1, r1, t串分割后得到l2, r2

如果不交换：那么l1和l2应该互为扰乱字符串，r1和r2也应该互为扰乱字符串。
如果交换：那么l1和r2应该互为扰乱字符串，r1和l2页应该互为扰乱字符串。

得到状态转移方程：
$$dp[i][j]=trueif:\{\begin{array}{r}dp[i][j][k]\wedge dp[i+k][j+k][len-k]\\ or\\ dp[i][j+len-k][k]\wedge dp[i+k][j][len-k]\end{array}$$

D. 矩阵问题

练习题1：LeetCode 120. 三角形最小路径和

题目大意：给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

状态定义：设dp[i][j]表示到达第i行第j列的最小路径和。

初始状态：S为起点，没有别的路径可以到达S，因此dp[0][0]=triangle[0][0]

状态转移：

1. 对于 j=0 的格子，只有从上方来的路径，因此dp[i][j]=dp[i-1][0]+triangle[i][0]
2. 对于 j=i 的格子，只有从左上方来的路径，因此dp[i][j] = dp[i-1][j-1]+triangle[i][j]
3. 对于其他格子，均具有两条路径，正上方和左上方，因为我们要最小路径和，所以取两条路径的最小值，
   dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])+triangle[i][j]

最后返回dp[n-1]中的最小值

练习题2：LeetCode 64. 最小路径和

题目大意：给定一个 m x n 矩形 grid ，找出到达最右下角的位置的最小路径和。每一步只能向下或者向右移动一步。

状态定义：设dp[i][j]表示到达第i行第j列的最小路径和。

初始状态：S为起点，没有别的路径可以到达S，因此dp[0][0]=grid[0][0]

状态转移：

1. 对于 j=0 的格子，只有从上方来的路径，因此dp[i][j]=dp[i-1][0]+triangle[i][0]
2. 对于 i= 0 的格子，只有从左边来的路径，因此dp[i][j] = dp[i][j-1]+triangle[i][j]
3. 对于其他格子，均具有两条路径，上方和左方，因为我们要最小路径和，所以取两条路径的最小值，
   dp[i][j] = min(dp[i][j-1], dp[i-1][j])+triangle[i][j]

最后返回dp[m-1][n-1]

练习题3：LeetCode 221. 最大正方形

题目大意：给定一个 m x n 二维矩阵 ，找到只包含’1’的最大正方形，并返回其面积。

状态定义：设dp[i][j]表示以第i行第j列为右下角顶点的最大正方形边长。

初始状态：当matrix[i][[j]为1时，至少可以构成一个边长为1的正方形，dp[i][j]=1。

状态转移：

1. 对于 i=0和j=0 的格子，最多只能构成边长为1的正方形。dp[i][j]=matrix[i][j]-‘0’
2. 对于其他格子，如果matrix[i][j]为1，那么至少可以构成一个边长为1的正方形。同时，检查左边，左上，正上三个相邻格子的正方形边长，并取其中的最小值+1。为什么是这三个方向呢？因为我们定义dp[i][j]是以(i,j)为右下角顶点的正方形的最大边长，只有左边，左上，正上的都为有效正方形时，才能和(i,j)构成更大的正方形，且构成的正方形的边长为三个正方形边长中最短的那个（比如：1，1，2，那么构成新的正方形的边长为1+1=2）
3. 记录最大的边长，最后返回最大边长的平方，就是最大正方形的面积
   

练习题4：LeetCode 931. 下降路径最小和

题目大意：给定一个m x n的二维矩阵 ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 或者-1的三个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1或i-1 。

状态定义：设dp[i][j]表示到达第i行第j列的最小路径和。

初始状态：S为起点，没有别的路径可以到达S，因此dp[0][0]=triangle[0][0]

状态转移：

1. 对于 j=0 的格子，只有从上方或右上方来的路径，因此dp[i][j]=min(dp[i-1][0], dp[i-1][1])+triangle[i][0]
2. 对于 j=n-1的格子，只有从上方或者左上方的路径，因此dp[i][j]=min(dp[i-1][j-1], dp[i-1][j])+triangle[i][j]
3. 对于 i=0 的格子，没有可以到达这些格子的路径，均为路径的起始点，因此dp[0][j] = triangle[0][j]
4. 对于其他格子，均具有三条路径，正上方，左上方，右上方，因为我们要最小路径和，所以取三条路径的最小值，
   dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])+triangle[i][j]
5. 最后返回dp最后一行的最小值

练习题5：LeetCode 174. 地下城游戏

题目大意：给定一个m x n的二维矩阵 ，每个格子有一个数值，正数增加当前分数，负数则减少当前分数，任何时刻，当分数小于等于0，游戏就会立刻失败。问，为了达到右下角的终点，初始分数至少需要多少？每次只能向右或者向下移动。

题目分析：本题同时包含两个信息：从出发位置到当前点的路径和，从出发点到达当前点所需要的最小初始值。我们有两种策略，1是选择路径和尽可能大的，这样在后序的探索中赢得游戏的概率大一些；2是选择需要初始分数最小的路径，这样是满足题目要求。然而，这两个策略的路径并不一定统一，可能存在不同选择，而我们很难判断究竟哪个策略是对的。此时，有两个同样重要的指标影响着我们的决策，不满足动态规划的无后效性。因此，我们需要换一个思路，固定一个变量——路径和，我们从终点倒序DP，让每一个路径都满足“到达终点的最小初始分数”，路径和只要保证大于0就行。

状态定义：设dp[i][j]表示从第i行第j列出发到达终点所需的最小初始分数。

初始状态：终点格子的分数如果是负数，则我们取其相反数+1，因为至少需要大于这个格子的负分数，才能保证不会游戏失败；如果分数为正数，则初始分数为1即可。dp[m-1][n-1]=max(1,-dungeon[m-1][n-1]+1)

状态转移：

1. 如果当前格子的分数为正数，且超过到达终点所需要的消耗，那么我们到达这一格时保证有1分维持游戏运行，再加上这一格的分时，就能顺利到达终点。因此，需要初始分数的为1分。
2. 如果当前格子时正数，但没有超过到达终点需要的消耗，那么我们需要补上差值即可，初始分数为当前格子与到达终点所需要的分数的差值
3. 如果当前格子为负数，那么就需要更大的初始分数，即到达终点的需要的分数+当前格子减去的分数
4. 对于 i=m-1 的格子，我们已经不能继续往下走了，只能往右走，dp[i][j] = max(1, dp[i][j+1]-dungeon[i][j]), 如果dungeon[i][j]为正数，那么计算的就是差值；如果差值为负，那么说明我们只要到达这个格子的时候有1分就行；如果为负数，那么得到的就是新的到达终点需要的分数的总和
5. 对于j=n-1的格子，我们已经不能继续向右走了，只能向下走，dp[i][j] = max(1, dp[i+1][j]-dungeon[i][j])
6. 对于其他格子，我们都有两种选择，走右和走下，选择需要初始分数最小的那一条，dp[i][j] = max(1,min(dp[i][j+1]-dungeon[i][j],dp[i+1][j]-dungeon[i][j]));
7. 最后返回dp[0][0]

E. 矩阵问题2: dp[i][j][k]，比起普通矩阵DP又多了一维信息

练习题：LeetCode 1444. 切披萨的方案数

题目大意：给你一个 rows x cols 大小的矩形披萨和一个整数 k ，矩形包含两种字符： ‘A’ （表示苹果）和 ‘.’ （表示空白格子）。你需要切披萨 k-1 次，得到 k 块披萨并送给别人。切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。

状态定义：设dp[i][j][k]表示，以(i,j)为左上角，(m-1,n-1)为右下角（固定）的披萨切k刀的方案数。apples[i][j]表示以(i,j)为左上角，(m-1,n-1)为右下角（固定）的披萨包含的苹果的数量。

初始状态：根据容斥定理计算apples[i][j]（ apples[i][j] += apples[i+1][j] + apples[i][j+1] - apples[i+1][j+1] ), 当apples[i][j]>0，dp[i][j][0]=1（表示一刀都不切的方案数）

状态转移：对于(i,j)为左上角，(m-1,n-1)为右下角（固定）的披萨，我们从k=1开始枚举切割次数，对于每个k，我们从x=i+1开始枚举切割的横坐标，如果切割后，剩下的部分有苹果，则属于合法方案，dp[i][j][k] = (dp[i][j][k]+dp[x][j][k-1])%MOD，dp[x][j][k-1]表示剩余的部分切k-1刀的方案；类似的，我们枚举y=j+1，dp[i][j][k] = (dp[i][j][k]+dp[i][y][k-1])%MOD。

F. 无串线性问题

练习题1：LeetCode650. 只有两个键的键盘

题目大意：最初记事本上只有一个字符 ‘A’ 。你每次可以对这个记事本进行两种操作：

1. Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
2. Paste（粘贴）：粘贴 上一次 复制的字符。

给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 ‘A’ 。返回能够打印出 n 个 ‘A’ 的最少操作次数。

状态定义：设dp[i]表示得到长度为i的A串需要的最少操作次数

初始状态：dp[1]=0，因为最初是就有一个‘A’，所以无需任何操作就能得到长度为1的A， 其余dp初始化为INT_MAX

状态转移：对于j<=i, 如果i%j==0，那么我们可以通过复制长度为j的A串 i/j 次达到A，需要的操作数为 dp[i] = dp[j]+i/j

练习题2：LeetCode650. 只有两个键的键盘

题目大意：最初记事本上只有一个字符 ‘A’ 。你每次可以对这个记事本进行两种操作：

1. Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
2. Paste（粘贴）：粘贴 上一次 复制的字符。

给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 ‘A’ 。返回能够打印出 n 个 ‘A’ 的最少操作次数。

状态定义：设dp[i]表示得到长度为i的A串需要的最少操作次数

初始状态：dp[1]=0，因为最初是就有一个‘A’，所以无需任何操作就能得到长度为1的A， 其余dp初始化为INT_MAX

状态转移：对于j<=i, 如果i%j==0，那么我们可以通过复制长度为j的A串 i/j 次达到A，需要的操作数为 dp[i] = dp[j]+i/j

优化：对于i的因子j，必有一个对称因子i/j，因此，我们可以只枚举$\sqrt{i}$个j，然后分别取两个因子的最小值，即：
$$dp[i]=min(dp[i],min(dp[i/j]+j,dp[j]+i/j))$$

练习题3：LeetCode264. 丑数II

题目大意：给你一个整数 n ，请你找出并返回第 n 个 丑数 。丑数 就是只包含质因数 2、3 和/或 5 的正整数。

状态定义：设dp[i]表示第i个丑数

初始状态：dp[1]=1， 设定三个指针，two，three，five，分别代表包含质因子2，3，5的丑数的下标，初始为1

状态转移：丑数，一定来源于之前的丑数与2，3，5的乘积。每次取 2*dp[two], 3*dp[three], 5*dp[five]中的最小值。如果得到的丑数是2的倍数，则two++；如果是3的倍数，则three++；如果是5的倍数，则five++。注意，有的丑数包含多个质因子，对应的指针均需要右移。

练习题4：LeetCode279. 完全平方数

题目大意：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

状态定义：设dp[i]表示i的完全平方数的最少数量

初始状态：dp[i] = i，至多由i个1组成

状态转移：从j=1开始枚举，如果$j^2\le i$，那么将$j^2$作为最后一个完全平方数，则i的完全平方数就等于$i-j^2$的完全平方数+1。即：
$$dp[i]=min(dp[i],dp[i-j\ast j]+1)$$

练习题5：LeetCode343. 整数拆分

题目大意：给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

状态定义：设dp[i]表示将i拆分得到的最大乘积

初始状态：dp[i] = 1，将i拆成i个1相乘，得到1

状态转移：从i=2开始枚举，对于j<i，我们可以得到两个部分，(i-j) 和j，如果我们仅拆分这一次，那么乘积为(i-j) *j，如果我们继续拆分剩下的部分，那么乘积等为dp(i-j)*j。得到状态转移方程：
$$dp[i]=max(dp[i],max(dp[i-j]\ast j,(i-j)\ast j))$$

最后

以上就是活泼发箍为你收集整理的【从零开始的动态规划02】——双串问题dp[i][j]，矩阵DP，无串线性DP的全部内容，希望文章能够帮你解决【从零开始的动态规划02】——双串问题dp[i][j]，矩阵DP，无串线性DP所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。