Day 10

1.最长回文子串

最长回文子串
枚举、字符串、dp

1.1 解析

1.2 代码

//中心扩展算法int getLongestPalindrome(string s) {int n=s.size();int len=1;//统计结果for(int i=0;i<n;i++)//枚举中心点{//当长度是奇数的时候int left=i-1,right=i+1;while(left>=0&&right<n&&s[left]==s[right]){left--;right++;}len=max(len,right-left-1);//当长度是偶数的时候left=i,right=i+1;while(left>=0&&right<n&&s[left]==s[right]){left--;right++;}len=max(len,right-left-1);}return len;}//方法二：动态规划
void ToLower(string& s){for(auto& e:s){if(e>='A'&&e<='Z') e+=32;}}int getLongestPalindrome(string s) {//1.准备工作ToLower(s);//2.创建dp表+初始化int n=s.size();vector<vector<bool>> dp(n,vector<bool>(n));//3.填表int maxlen=1;//记录回文串的长度for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s[i]==s[j]){dp[i][j]=i+1<j?dp[i+1][j-1]:true;if(dp[i][j]&&maxlen<(j-i+1)){maxlen=j-i+1;}}}}return maxlen;}

2.买卖股票的最好时机(一)

买卖股票的最好时机(一)
贪心、线性dp

2.1 解析

2.2 代码

#include <iostream>
#include <vector>
using namespace std;int main()
{int n=0;cin>>n;vector<int> nums(n);for(int i=0;i<n;i++) cin>>nums[i];int ret=0;//记录结果int prevmin=nums[0];for(int i=1;i<n;i++){prevmin=min(prevmin,nums[i-1]);if(ret<nums[i]-prevmin)ret=nums[i]-prevmin;}cout<<ret;return 0;
}

3.[NOIP2002 普及组] 过河卒

[NOIP2002 普及组] 过河卒
二维dp

3.1 解析

3.2 代码

#include <iostream>
#include <vector>
using namespace std;int main()
{int n,m,x,y;cin>>n>>m>>x>>y;x+=1,y+=1;//1.创建dp表vector<vector<long long>> dp(n+2,vector<long long>(m+2));//2.初始化dp[0][1]=1;//3.填表for(int i=1;i<=n+1;i++){for(int j=1;j<=m+1;j++){if((i==x&&j==y)||(abs(i-x)+abs(j-y)==3&&i!=x&&j!=y))dp[i][j]=0;else dp[i][j]=dp[i-1][j]+dp[i][j-1];}}cout<<dp[n+1][m+1];return 0;
}