目录
1、最长回文子串
1.1 题目
1.2 思路
1.3 代码实现
2、买卖股票的最好时机
2.1 题目
2.2 思路
2.3 代码实现
3、过河卒
3.1 题目
3.2 思路
3.3 代码实现
1、最长回文子串
1.1 题目
1.2 思路
根据题目可知，在一个长度为n的字符串中求得最长回文子串的长度，回文子串可以理解为对称的字符串。因为具有对称性，那么就可一使用中心拓展的思路，依次遍历字符串，每一个字符向两边拓展，直至结束。
1.3 代码实现
注意一下字符串的长度要分奇数和偶数的情况
class Solution
{
public:int getLongestPalindrome(string A) {int left =0,right = 0,ret = 0;//当字符串长度为偶数时for(int i = 0; i < A.size();i++){left = i,right = i+1;while(left >= 0 && right <=A.size() && A[left] == A[right]){left--,right++;}ret = max(ret,right-left-1);}//为奇数for(int j = 0; j < A.size();j++){left = j,right = j;while(left >= 0 && right <=A.size() && A[left] == A[right]){left--,right++;}ret = max(ret,right-left-1);}return ret;}
};
2、买卖股票的最好时机
2.1 题目
2.2 思路
根据题目只能买卖一次，求得获得利润的最高收益，无论亏损多少，只要没有利润就输出0。那么我们首先就能暴力求解，遍历数组求得每一组的利润，返回最大值，但是暴力求解用了两层for循环，所以会超时。
因此需要再次基础上做优化，暴力求解是回溯重复了太多次，所以我们逆向思维，先考虑卖出的价值，然后就只需要求得该卖点之前的最小价值即可，得到的差就是最大值。
理清思路，接下来就是代码实现。
2.3 代码实现
注意一下，minval和ret的顺序，先求最小值，要考虑自身位置，这样利润最小也是0，不会为负
#include <iostream>
using namespace std;int main()
{int n = 0;cin >> n;int arr[n];for(int i = 0;i < n;i++)cin >> arr[i];int ret = 0,minval = arr[0];for(int i= 0; i < n;i++){minval = min(arr[i],minval);ret = max(ret,arr[i]-minval);}cout << ret << endl;return 0;
}
3、过河卒
3.1 题目
3.2 思路
这是一道经典的动态规划题，读完题，要注意马能到达及其所在的位置不能走，马一开始就给出了固定点，且题中也给出了，马能跳跃的点与其所在位置的关系。
注意：
- 棋盘的大小是(n+1,m+1)。
- 注意边界控制，从[1,n+1][1,m+1]遍历
- 分情况：
- a.判断马的控制点阻塞路径，和重合问题
- b.正常执行状态转移方程dp[i][j] = dp[i][j-1] + dp[i-1][j]
创建dp表时，多一行，多一列，初始化dp[0][0] = 0; dp[0][1]或者dp[1][0] = 1;
3.3 代码实现
这道题数据范围很大所以记得用 long long初始化dp表
#include <iostream>
using namespace std;long long dp[24][24];int main()
{int n,m,x,y;cin >> n >> m >> x >> y;dp[0][1] = 1;x += 1, y+=1;//dp表创建的时候多了一行多了一列，为了找原数组映射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;elsedp[i][j] = dp[i][j-1] + dp[i-1][j];}}cout << dp[n+1][m+1] << endl;return 0;
}
本篇完，下篇见！
