目录
028：最长回文子串
029：买卖股票的最好时机（一）
030：过河卒
028：最长回文子串
最长回文子串_牛客题霸_牛客网 (nowcoder.com)
题目：
题解：
1.中心扩展算法：
- 每个字符都可以尝试作为中心点看，会出现两种情况：可能是类似 aba 的字符串，也可能是类似 abba 的情况
- 只需要分别计算出以一个和两个字符作为中心点的子串，取出较大的长度即可
- 从left到right开始向两边扩散、比较，如果相等则继续扩散比较
- 如果不相等则剪枝，不用再继续扩散比较
- 计算每次比较的回文子串长度，取最大
class Solution {
public:
int getLongestPalindrome(string s)
{
//中心扩展算法
int n=s.size();
int ret=0;
for(int i=0;i<n;i++) //枚举中心点
{
//长度为奇数时
int left=i-1,right=i+1;
while(left>=0 && right<=n-1 && s[left]==s[right])
{
left--;
right++;
}
ret=max(ret,right-left-1);
//长度为偶数
left=i,right=i+1;
while(left>=0 && right<=n-1 && s[left]==s[right])
{
left--;
right++;
}
ret=max(ret,right-left-1);
}
return ret;
}
};029：买卖股票的最好时机（一）
买卖股票的最好时机(一)_牛客题霸_牛客网 (nowcoder.com)
题目：
题解：
贪心：边遍历边固定最小价格为买入点，当天为卖出点，同时更新维护最大利润。
#include <iostream>
using namespace std;
const int MAX=1e5+5;
int main()
{
int prices[MAX]={0};
int n=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>prices[i];
}
int maxpro=-0x3f3f3f3f,minpri=0x3f3f3f3f;
for(int i=0;i<n;i++)
{
minpri=min(minpri,prices[i]); //下标i之前的最小价格
maxpro=max(maxpro,prices[i]-minpri); //到当天的为止的最大利润
}
cout<<maxpro<<endl;
return 0;
}
030：过河卒
[NOIP2002 普及组] 过河卒_牛客题霸_牛客网 (nowcoder.com)
题目：
题解：
动态规划-路径类：
1.状态表示：
dp[i][j]：从[0,0]位置出发，到达[i,j]位置一共有多少种方法
2.状态转移方程：
dp[i][j]=0（[i,j]位置有马拦时）
dp[i][j]=dp[i-1][j]+dp[i][j-1](可以正常通行)
3.初始化：
和原棋盘比较，多加一行一列，dp[0][1]=1，其它为0。
4.填表：
填表时，为配合填dp表，棋盘下标和马位置整体加1，dp[n+1][m+1]为到B点时的结果。
#include <iostream>
using namespace std;
int n, m, x, y;
long long dp[25][25];
int main() {
cin >> n >> m >> x >> y;
x += 1;
y += 1;
dp[0][1] = 1;
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 || (x == i && y == j)) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
cout << dp[n + 1][m + 1] << endl;
return 0;
}
// 64 位输出请用 printf("%lld")
