学习笔记.动态规划"/>
cyx的学习笔记.动态规划
什么是动态规划?
动态规划(英语:Dynamic programming,简称 DP),是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。我个人对它的理解就是一个大问题分解为几个个小问题,并且将小问题的答案存储起来。
动态规划用法:
首先确定边界,确定问题的参数边界(包括起始的值);然后是找规律,确定最优子结构;最后是寻找状态转移方程,之后就可以用代码实现了。
例1牛客华为机试面试题HJ75公共子串计算:
描述
给定两个只包含小写字母的字符串,计算两个字符串的最大公共子串的长度。
注:子串的定义指一个字符串删掉其部分前缀和后缀(也可以不删)后形成的字符串。
数据范围:字符串长度:1\le s\le 150\1≤s≤150
进阶:时间复杂度:O(n^3)\O(n3) ,空间复杂度:O(n)\O(n)
输入描述:
输入两个只包含小写字母的字符串
输出描述:
输出一个整数,代表最大公共子串的长度
int dp[m+1][n+1];
首先确定边界
for(int i = 0; i <= m; ++i) dp[i][0] = 0;
for(int j = 0; j <= n; ++j) dp[0][j] = 0;
dp[i][j] str1前i个字符和str2前j个字符(以其为尾字符)的最长公共子串长度
然后就是寻找最佳子结构
我们可以发现不在边界上的话,如果str1[i-1] == str2[j-1]时,如果要寻找最长的公共子字符串,应该用两个指针分别遍历str1,str2,遍历时当两个指针i,j相同时,可以观察i+1与j+1的值是否相同。
for(int i = 1; i <= m; ++i) {for(int j = 1; j <= n; ++j) {if(str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = 0;if(dp[i][j] > maxlen) {maxlen = dp[i][j];}}
将最大值存储在dp[i][j]中,通过maxlen与dp[i][j]的比较来取得最大公共子串。
全部题解
#include <bits/stdc++.h>
using namespace std;
int maxsubstr(const string& str1,const string& str2) {int m = str1.length();int n = str2.length();int dp[m+1][n+1];int maxlen = 0;for(int i = 0; i <= m; ++i) dp[i][0] = 0;for(int j = 0; j <= n; ++j) dp[0][j] = 0;for(int i = 1; i <= m; ++i) {for(int j = 1; j <= n; ++j) {if(str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = 0;if(dp[i][j] > maxlen) {maxlen = dp[i][j];}}}return maxlen;
}
int main(){string s1,s2;cin>>s1>>s2;cout<<maxsubstr(s1,s2);
}
更多推荐
cyx的学习笔记.动态规划
发布评论