1.最长回文子串
思路：
常规思路就是dp。dp[i][j]表示字符串i-j是否是回文子串。
如果A[i]==A[j]，考虑以下几种情况：
长度小于3，说明一定是回文。
要想让dp[i][j]为真，则dp[i+1][j-1]必须也为真。否则就是false.即dp[i][j]=dp[i+1][j-1]
顺便用一个ans维护一下答案就好了
这种做法的复杂度是N^2.还有一种叫马拉夫的做法，On的复杂度，但是我忘了，草。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 class Solution { public: int getLongestPalindrome(string A) { int n = A.size(); vector<vector<bool>> dp(n + 1, vector<bool>(n + 1)); if (A.size() == 1)return 1; for (int i = 1; i <= n; i++) { dp[i][i] = true; } int ans = 1; for (int len = 1; len <= n; len++) { for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; if (len == 1)continue; if (A[l - 1] != A[r - 1]) { dp[l][r] = false; } else { if (len <= 3)dp[l][r] = true; else dp[l][r] = dp[l + 1][r - 1]; } if (dp[l][r])ans = max(ans, r - l + 1); } } return ans; } };
2.买股票的最佳时机（一）
思路：
暴力枚举。假设我们在第i天买入，那么在什么时候卖掉最合适呢？在第i天之后哪一天的票价最高我们就在哪一天卖掉。所以我们可以再用一个数组s[]，s[i]表示i-n天的最高票价
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> using namespace std; const int N = 1e5 + 10; int a[N]; int s[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } s[n] = a[n]; for (int i = n - 1; i >= 1; i--) { s[i] = max(s[i + 1], a[i]); } int ans = 0; for (int i = 1; i < n; i++) { ans = max(ans, s[i + 1] - a[i]); } cout << ans; return 0; }
3.过河卒
思路：
一眼看上去dfs，做了一遍直接超时了（优化一下应该就能过）。后来换了种思路，借用类似杨辉三角的做法。
dp[i][j]表示，从起点到(i,j)的路径有多少。如果没有马的干扰，那么dp[i][j]=dp[i-1][j]+dp[i][j-1]
首先如果i,j本身就是马的范围，那么直接滚，表示走到这个点的路径数0。
换而言之，就是遇到马步直接跳过。
代码：
#include <iostream> #include<queue> #include<algorithm> using namespace std; const int N = 50; long long f[N][N]; bool st[N][N]; int n, m, x, y; int dx[] = { 0, -2, -1, 1, 2, 2, 1, -1, -2 }; int dy[] = { 0, 1, 2, 2, 1, -1, -2, -2, -1 }; bool check(int a, int b) { if (x == a && y == b)return false; if (abs(a - x) + abs(b - y) == 3) { return false; } // cout<<abs(a - x) + abs(b - y) <<"--"<<endl; return true; } int main() { int n, m, x, y; cin >> n >> m >> x >> y; if (n == x && m == y) { cout << 0 << endl; return 0; } for (int i = 0; i < 9; i++) { int a = x + dx[i]; int b = y + dy[i]; if (a >= 0 && a <= n && b >= 0 && b <= m)st[a][b] = true; } for (int i = 1; i <= m; i++) { if (st[0][i]) { break; } f[0][i] = 1; //cout<<i<<" "; } for (int i = 1; i <= n; i++) { if (st[i][0]) { break; } f[i][0] = 1; //cout<<i<<" "; } f[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (st[i][j])continue; if (!st[i - 1][j])f[i][j] += f[i - 1][j]; if (!st[i][j - 1])f[i][j] += f[i][j - 1]; // cout<<f[i][j]<<" "; } //cout<<endl; } cout << f[n][m] << endl; return 0; }
