建设网站方面的证书,动漫制作专业介绍心得体会200字,女教师网课入06654侵录屏,网站网站平台建设方案最近开始接触动态规划问题#xff0c;以下浅谈#xff08;或回顾#xff09;一下这些问题的求解过程。解题思路对于动态规划问题#xff0c;由于最终问题的求解需要以同类子问题作为基础#xff0c;故需要定义一个dp数组#xff08;一维或二维#xff09;来记录问题求解…最近开始接触动态规划问题以下浅谈或回顾一下这些问题的求解过程。解题思路对于动态规划问题由于最终问题的求解需要以同类子问题作为基础故需要定义一个dp数组一维或二维来记录问题求解的各个状态避免多次求算重复子问题然后就是确认状态转移方程也就是问题求解的递推公式由于问题的最终状态需要从最初状态递推而来故需初始化状态即初始化dp数组。步骤如下确定dp数组以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组上述步骤来自代码随想录爬楼梯问题爬楼梯时每一次只能上1级或2级阶梯问爬n级阶梯有多少种方法这是一个最简单的动态规划问题以下是解题步骤定义数组int dp[1005],根据问题的问法设dp[n]表示爬n级楼梯时的方法总数;确认状态转移方程我们直接考虑最后一次爬上n级楼梯的方法。显然最后一次无非直接爬1级阶梯上到第n级或者爬2级阶梯上到了第n级。由于前者是发生在已爬n-1级阶梯的基础上而后者发生在已爬n-2级阶梯的基础上。故爬n级阶梯的方法总数等于dp[n-1]dp[n-2],即转台转移方程dp[n] dp[n-1]dp[n-2]确定初始状态,显然dp[n]需要从两个子状态推导而来故问题的边界为确认dp[1]与dp[2].易知,dp[1]1,dp[2]2;确定遍历顺序,显然需要从dp[1]与dp[2]往后递推。第一种情况第二种情况图来自小灰漫画)#includeiostream
using namespace std;//dp[i]表示爬i级阶梯时所花费的步数
int dp[1005];
int main() {int n;cin n;//初始化dp[1] 1;dp[2] 2;//递推公式为:dp[i] dp[i-1]dp[i-2] (i3)for (int i 3;i n;i) {dp[i] dp[i - 1] dp[i - 2];}cout dp[n] endl;return 0;
}求最大子段问题描述给定一个数字序列称由连续元素组成的序列为该数字序列的子段问子段元素之和的最大值为何由于每一个子段必有一个前缀与后缀最大子段必有一个前缀或者后缀我们干脆定义dp[i]表示以序列中第i个元素为后缀的最大子段定义int a[1005]存储数字序列的各个元素a[i]表示序列中的第i个元素。解题步骤如下定义int dp[1005],dp[i]表示以序列中第i个元素为后缀的最大子段确认状态转移方程每一个元素可以单独作为一个子段因此对于dp[i]而言其最大子串无非两种情况第一若dp[i-1]0那么a[i]单独作为子段其必定小于第i元素与以序列中第i-1个元素为后缀的最大子段拼接所得到得新子段此时dp[i] dp[i-1]a[i];若dp[i-1]0,那么a[i]单独作为子段会使dp[i]更大故dp[i]a[i]。即转移方程为dp[i]max(dp[i-1]a[i],a[i])确认初始状态显然获取dp[i]需要得知dp[i-1]即dp[1]a[1]确定遍历顺序显然从左往右扫描即可。#includeiostream
using namespace std;
const int maxn 1005;
int a[maxn];
int dp[maxn];int main() {int n;cin n;for (int i 1;i n;i) {cin a[i];}dp[1] a[1];for (int i 2;i n;i) {dp[i] max(dp[i - 1] a[i], dp[i]);}int max dp[1];for (int i 2;i n;i) {if (max dp[i]) {max dp[i];}}cout max endl;return 0;
}求最长上升子序列问题描述给定一个数字序列取其中的部分元素元素无需连续要求元素按升序排列问上升子序列的最大长度也就是该子序列里面元素的最大个数。依旧定义int dp[1005]其中dp[i]表示以序列中第i个元素为结尾的最长上升子序列。对于dp[i]最长上升子序列与后面元素有关若a[i]a[i-1]那么必定有dp[i]dp[i-1]1,可在a[i]后面的元素中dp[i-1]并不一定就是最大的依旧需要遍历dp[1]~dp[i-1]中满足a[j]a[i]且a[j]最大的那个上升子序列从而接到a[i]后面解题思路如下定义int dp[1005],dp[i]表示以序列中第i个元素为结尾的最长上升子序列确认递推公式,dp[i] max(dp[i-1],dp[i-2],..........,dp[1])1确认初始化状态显然每一个元素的都至少可以单独构成一个长度为1的最长上升子序列从而设置dp[0]0,a[0]-inf (inf表示无穷大)保证序列中每一个元素都至少能大于a[0];确认遍历顺序依旧是从左往右扫描。#includeiostream
using namespace std;const int maxn 1005;
int a[maxn];
int dp[maxn];
const int inf 0xffffff;//求最长子序列假设dp[i]表示以第i元素为结尾的最长上升子序列int main(){int n;cin n;a[0] -inf;for (int i 1;i n;i) {cin a[i];}int ans 0;for (int i 1;i n;i) {for (int j 0;j i;j) {if (a[i] a[j]) {dp[i] max(dp[i], dp[j] 1);}}ans max(ans, dp[i]);}cout ans endl;return 0;
}求最大公共子串问题描述给定两个字符串a,b,求a与b中公共部分的元素个数.例如aabfed,bbfd,那么最大公共子串ps bfd,其元素个数为3.此时假定一个二维数组int dp[1005][1005],那么dp[i][j]表示a前i个字符构成的子串与b前j个字符构成的子串的最大公共子串。那么此时若a[i-1]b[j-1],说明字符串a的第i个字符与字符串b的第j个字符相等那么此时dp[i][j]dp[i-1][j-1]1;若a[i-1]!b[j-1],dp[i][j]max(dp[i-1][j],dp[i][j]),因为父串a与其他串b的最大子串一定大于或等于该父串a的子串与其他串b的最大子串.解题思路定义int dp[1005][1005],dp[i][j]表示a前i个字符构成的子串与b前j个字符构成的子串的最大公共子串确认递推公式,若a[i-1]b[j-1],则dp[i][j]dp[i-1][j-1]1;否则dp[i][j]max(dp[i-1][j],dp[i][j]).确认初始化状态只需要初始化dp[0][0]0即可。确认遍历顺序依旧是从左往右从上往下扫描。#includeiostream
#includestring
#includecstdiousing namespace std;
int dp[105][105];
int main() {string a, b;cin a b;int lena a.length();int lenb b.length();memset(dp, 0, sizeof(dp));for (int i 1;i lena;i) {for (int j 1;j lenb;j) {if (a[i - 1] b[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;}else {dp[i][j] max(dp[i][j - 1], dp[i - 1][j]);}}}cout dp[lena][lenb] endl;return 0;
}求编辑距离问题描述给定一个字符串S与一个模板字符串T可以对S进行插、替、删三种操作问S经过上述操作变为T的最少次数即为最小编辑距离。依旧设int dp[1005][1005]其中dp[i][j]表示S的前i个字符与T的前j个字符的最小编辑距离。解题思路定义int dp[1005][1005],dp[i][j]表示S的前i个字符与T的前j个字符的最小编辑距离确认递推公式,若a[i-1]b[j-1],则dp[i][j]dp[i-1][j-1];否则在dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j]中若dp[i-1][j-1]最小说明需要将a[i-1]替换为b[j-1];若dp[i][j-1]最小需要在S的前i个字符后面添加一个b[j-1];若dp[i-1][j]最小需要删除a[i-1]。即dp[i][j]min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])1;确认初始化状态需要依次初始化dp[0][0]~dp[0][S.length()]以及dp[T.length()][0];确认遍历顺序依旧是从左往右从上往下扫描。#includeiostream
#includestring
using namespace std;int dp[105][105];//dp[i][j]表示S前i个字符与T前j个字符编辑时的最小距离//求编辑距离
int func(string S,string T) {int lenS;int lenT;lenS S.length();lenT T.length();dp[0][0] 0;for (int i 1;i lenS;i) {dp[i][0] i;}for (int j 1;j lenT;j) {dp[0][j] j;}for (int i 1;i lenS;i) {for (int j 1;j lenT;j) {if (S[i - 1] T[j - 1]) {dp[i][j] dp[i - 1][j - 1];}else {dp[i][j] min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) 1;}}}return dp[lenS][lenT];
}int main() {string S, T;cin S T;cout func(S, T) endl;return 0;
}
