2023年8月1日发(作者：)
动态规划问题-经典模型的状态转移⽅程状态转移⽅程动态规划中当前的状态往往依赖于前⼀阶段的状态和前⼀阶段的决策结果。例如我们知道了第i个阶段的状态Si以及决策Ui，那么第i+1阶段的状态Si+1也就确定了。所以解决动态规划问题的关键就是确定状态转移⽅程，⼀旦状态转移⽅程确定了，那么我们就可以根据⽅程式进⾏编码。在前⾯的⽂章讲到了如何设计⼀个动态规划算法，有以下四个步骤：1、刻画⼀个最优解的结构特征。2、递归地定义最优解的值。3、计算最优解的值，通常采⽤⾃底向上的⽅法。4、利⽤计算出的信息构造⼀个最优解。对于确定状态转移⽅程就在第⼀步和第⼆步中，⾸先要确定问题的决策对象，接着对决策对象划分阶段并确定各个阶段的状态变量，最后建⽴各阶段的状态变量的转移⽅程。例如⽤dp[i]表⽰以序列中第i个数字结尾的最长递增⼦序列长度和最长公共⼦序列中⽤dp[i][j]表⽰的两个字符串中前 i、 j 个字符的最长公共⼦序列，我们就是通过对这两个数字量的不断求解最终得到答案的。这个数字量就被我们称为状态。状态是描述问题当前状况的⼀个数字量。⾸先，它是数字的，是可以被抽象出来保存在内存中的。其次，它可以完全的表⽰⼀个状态的特征，⽽不需要其他任何的辅助信息。最后，也是状态最重要的特点，状态间的转移完全依赖于各个状态本⾝，如最长递增⼦序列中，dp[x]的值由 dp[i](i < x)的值确定。若我们在分析动态规划问题的时候能够找到这样⼀个符合以上所有条件的状态，那么多半这个问题是可以被正确解出的。所以说，解动态规划问题的关键，就是寻找⼀个好的状态。总结下⾯对这⼏天的学习总结⼀下，将我遇到的各种模型的状态转移⽅程汇总如下：1、最长公共⼦串假设两个字符串为str1和str2，它们的长度分别为n和m。d[i][j]表⽰str1中前i个字符与str2中前j个字符分别组成的两个前缀字符串的最长公共长度。这样就把长度为n的str1和长度为m的str2划分成长度为i和长度为j的⼦问题进⾏求解。状态转移⽅程如下：1. dp[0][j] = 0; (0<=j<=m)2. dp[i][0] = 0; (0<=i<=n)3. dp[i][j] = dp[i-1][j-1] +1; (str1[i] == str2[j])4. dp[i][j] = 0; (str1[i] != str2[j])因为最长公共⼦串要求必须在原串中是连续的，所以⼀但某处出现不匹配的情况，此处的值就重置为0。详细代码请看。2、最长公共⼦序列区分⼀下，最长公共⼦序列不同于最长公共⼦串，序列是保持⼦序列字符串的下标在str1和str2中的下标顺序是递增的，该字符串在原串中并不⼀定是连续的。同样的我们可以假设dp[i][j]表⽰为字符串str1的前i个字符和字符串str2的前j个字符的最长公共⼦序列的长度。状态转移⽅程如下：1. dp[0][j] = 0; (0<=j<=m)2. dp[i][0] = 0; (0<=i<=n)3. dp[i][j] = dp[i-1][j-1] +1; (str1[i-1] == str2[j-1])4. dp[i][j] = max{dp[i][j-1],dp[i-1][j]}; (str1[i-1] != str2[j-1]) 详细代码请看。3、最长递增⼦序列（最长递减⼦序列）因为两者的思路都是⼀样的，所以只给出最长递增⼦序列的状态转移⽅程。假设有序列{a1,a2,...,an}，我们求其最长递增⼦序列长度。按照递推求解的思想，我们⽤F[i]代表若递增⼦序列以ai结束时它的最长长度。当 i 较⼩，我们容易直接得出其值，如 F[1] = 1。那么，如何由已经求得的 F[i]值推得后⾯的值呢？假设，F[1]到F[x-1]的值都已经确定，注意到，以ax 结尾的递增⼦序列，除了长度为1的情况，其它情况中，ax都是紧跟在⼀个由 ai(i < x)组成递增⼦序列之后。要求以ax结尾的最长递增⼦序列长度，我们依次⽐较 ax 与其之前所有的 ai(i < x)，若ai⼩于 ax，则说明ax可以跟在以ai结尾的递增⼦序列之后，形成⼀个新的递 增⼦序列。⼜因为以ai结尾的递增⼦序列最长长度已经求得，那么在这种情况下，由以 ai 结尾的最长递增⼦序列再加上 ax 得到的新的序列，其长度也可以确定，取所有这些长度的最⼤值，我们即能得到 F[x]的值。特殊的，当没有ai(i < x)⼩ 于ax， 那么以 ax 结尾的递增⼦序列最长长度为1。 即F[x] = max{1,F[i]+1|ai
{
for (int j = 0;j <= V;j++) //枚举背包容量
{
f[i][j] = f[i - 1][j];
if (j >= v[i])
{
f[i][j] = Max(f[i - 1][j],f[i - 1][j - v[i]] + c[i]);
}
}
}
View Code可以参照、、7、矩阵连乘（矩阵链问题）-参考《算法导论》例如矩阵链 dp[1][n]即为最终求解.#define MAXSIZE 100int dp[MAXSIZE][MAXSIZE];//存储最⼩的就算次数int s[MAXSIZE][MAXSIZE];//存储断点，⽤在输出上⾯int i, j, tmp；for (int l = 2; l <= n; l++){//j-i的长度,由于长度为1是相同的矩阵那么为0不⽤计算 for (i = 1; i <= n - l + 1; i++){//由于j-i =l - 1 , 那么j的最⼤值为n，所以i上限为 n - l+1; j = i + l - 1;//由于j-i = l - 1 , 那么j = l+i-1 dp[i][j] = dp[i + 1][j] + r[i] * c[i] * c[j];//初始化，就是k = i； s[i][j] = i; for (k = i + 1; k < j; k++){//循环枚举k i < k < j tmp = dp[i][k] + dp[k + 1][j] + r[i] * c[k] * c[j]; if (dp[i][j] > tmp){ dp[i][j] = tmp;//更新为最⼩值 s[i][j] = k; } } }}//递归调⽤输出void output(int i, int j){ if (i == j){ printf("A%d", i);//当两个相等的时候就不⽤继续递归就输出A return;//返回上⼀层 } else{ printf("("); output(i, s[i][j]); printf(" x "); output(s[i][j] + 1, j); printf(")"); }}View Codeps如有错误的地⽅或者本⼈理解错的地⽅，请指出，共同进步
2023年8月1日发(作者：)
动态规划问题-经典模型的状态转移⽅程状态转移⽅程动态规划中当前的状态往往依赖于前⼀阶段的状态和前⼀阶段的决策结果。例如我们知道了第i个阶段的状态Si以及决策Ui，那么第i+1阶段的状态Si+1也就确定了。所以解决动态规划问题的关键就是确定状态转移⽅程，⼀旦状态转移⽅程确定了，那么我们就可以根据⽅程式进⾏编码。在前⾯的⽂章讲到了如何设计⼀个动态规划算法，有以下四个步骤：1、刻画⼀个最优解的结构特征。2、递归地定义最优解的值。3、计算最优解的值，通常采⽤⾃底向上的⽅法。4、利⽤计算出的信息构造⼀个最优解。对于确定状态转移⽅程就在第⼀步和第⼆步中，⾸先要确定问题的决策对象，接着对决策对象划分阶段并确定各个阶段的状态变量，最后建⽴各阶段的状态变量的转移⽅程。例如⽤dp[i]表⽰以序列中第i个数字结尾的最长递增⼦序列长度和最长公共⼦序列中⽤dp[i][j]表⽰的两个字符串中前 i、 j 个字符的最长公共⼦序列，我们就是通过对这两个数字量的不断求解最终得到答案的。这个数字量就被我们称为状态。状态是描述问题当前状况的⼀个数字量。⾸先，它是数字的，是可以被抽象出来保存在内存中的。其次，它可以完全的表⽰⼀个状态的特征，⽽不需要其他任何的辅助信息。最后，也是状态最重要的特点，状态间的转移完全依赖于各个状态本⾝，如最长递增⼦序列中，dp[x]的值由 dp[i](i < x)的值确定。若我们在分析动态规划问题的时候能够找到这样⼀个符合以上所有条件的状态，那么多半这个问题是可以被正确解出的。所以说，解动态规划问题的关键，就是寻找⼀个好的状态。总结下⾯对这⼏天的学习总结⼀下，将我遇到的各种模型的状态转移⽅程汇总如下：1、最长公共⼦串假设两个字符串为str1和str2，它们的长度分别为n和m。d[i][j]表⽰str1中前i个字符与str2中前j个字符分别组成的两个前缀字符串的最长公共长度。这样就把长度为n的str1和长度为m的str2划分成长度为i和长度为j的⼦问题进⾏求解。状态转移⽅程如下：1. dp[0][j] = 0; (0<=j<=m)2. dp[i][0] = 0; (0<=i<=n)3. dp[i][j] = dp[i-1][j-1] +1; (str1[i] == str2[j])4. dp[i][j] = 0; (str1[i] != str2[j])因为最长公共⼦串要求必须在原串中是连续的，所以⼀但某处出现不匹配的情况，此处的值就重置为0。详细代码请看。2、最长公共⼦序列区分⼀下，最长公共⼦序列不同于最长公共⼦串，序列是保持⼦序列字符串的下标在str1和str2中的下标顺序是递增的，该字符串在原串中并不⼀定是连续的。同样的我们可以假设dp[i][j]表⽰为字符串str1的前i个字符和字符串str2的前j个字符的最长公共⼦序列的长度。状态转移⽅程如下：1. dp[0][j] = 0; (0<=j<=m)2. dp[i][0] = 0; (0<=i<=n)3. dp[i][j] = dp[i-1][j-1] +1; (str1[i-1] == str2[j-1])4. dp[i][j] = max{dp[i][j-1],dp[i-1][j]}; (str1[i-1] != str2[j-1]) 详细代码请看。3、最长递增⼦序列（最长递减⼦序列）因为两者的思路都是⼀样的，所以只给出最长递增⼦序列的状态转移⽅程。假设有序列{a1,a2,...,an}，我们求其最长递增⼦序列长度。按照递推求解的思想，我们⽤F[i]代表若递增⼦序列以ai结束时它的最长长度。当 i 较⼩，我们容易直接得出其值，如 F[1] = 1。那么，如何由已经求得的 F[i]值推得后⾯的值呢？假设，F[1]到F[x-1]的值都已经确定，注意到，以ax 结尾的递增⼦序列，除了长度为1的情况，其它情况中，ax都是紧跟在⼀个由 ai(i < x)组成递增⼦序列之后。要求以ax结尾的最长递增⼦序列长度，我们依次⽐较 ax 与其之前所有的 ai(i < x)，若ai⼩于 ax，则说明ax可以跟在以ai结尾的递增⼦序列之后，形成⼀个新的递 增⼦序列。⼜因为以ai结尾的递增⼦序列最长长度已经求得，那么在这种情况下，由以 ai 结尾的最长递增⼦序列再加上 ax 得到的新的序列，其长度也可以确定，取所有这些长度的最⼤值，我们即能得到 F[x]的值。特殊的，当没有ai(i < x)⼩ 于ax， 那么以 ax 结尾的递增⼦序列最长长度为1。 即F[x] = max{1,F[i]+1|ai
{
for (int j = 0;j <= V;j++) //枚举背包容量
{
f[i][j] = f[i - 1][j];
if (j >= v[i])
{
f[i][j] = Max(f[i - 1][j],f[i - 1][j - v[i]] + c[i]);
}
}
}
View Code可以参照、、7、矩阵连乘（矩阵链问题）-参考《算法导论》例如矩阵链 dp[1][n]即为最终求解.#define MAXSIZE 100int dp[MAXSIZE][MAXSIZE];//存储最⼩的就算次数int s[MAXSIZE][MAXSIZE];//存储断点，⽤在输出上⾯int i, j, tmp；for (int l = 2; l <= n; l++){//j-i的长度,由于长度为1是相同的矩阵那么为0不⽤计算 for (i = 1; i <= n - l + 1; i++){//由于j-i =l - 1 , 那么j的最⼤值为n，所以i上限为 n - l+1; j = i + l - 1;//由于j-i = l - 1 , 那么j = l+i-1 dp[i][j] = dp[i + 1][j] + r[i] * c[i] * c[j];//初始化，就是k = i； s[i][j] = i; for (k = i + 1; k < j; k++){//循环枚举k i < k < j tmp = dp[i][k] + dp[k + 1][j] + r[i] * c[k] * c[j]; if (dp[i][j] > tmp){ dp[i][j] = tmp;//更新为最⼩值 s[i][j] = k; } } }}//递归调⽤输出void output(int i, int j){ if (i == j){ printf("A%d", i);//当两个相等的时候就不⽤继续递归就输出A return;//返回上⼀层 } else{ printf("("); output(i, s[i][j]); printf(" x "); output(s[i][j] + 1, j); printf(")"); }}View Codeps如有错误的地⽅或者本⼈理解错的地⽅，请指出，共同进步
发布评论