洛谷P1216数字三角形

记忆化搜索 但是一个TLE

#include<iostream>
using namespace std;
int n;
const int N = 1001;
int a[N][N], dp[N][N];
int dfs(int i, int j){if(i == n)return a[i][j];if(dp[i][j])return dp[i][j];dp[i][j] = max(dfs(i + 1, j), dfs(i + 1, j + 1)) + a[i][j];return dp[i][j];
}
int main(){cin >> n;for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++){cin >> a[i][j];}}cout << dfs(1, 1) << endl;return 0;
}

然后我们反着枚举

#include<iostream>
using namespace std;
int n;
const int N = 1001;
int a[N][N];
int main(){cin >> n;for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++){cin >> a[i][j];}}for(int i = n - 1; i >= 1; i--){for(int j = 1; j <= i; j++){a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);}}cout << a[1][1] << endl;return 0;
}

洛谷P1434滑雪：记忆化搜索

#include<iostream>
#include<climits>
using namespace std;
int n, m;
const int N = 105;
int a[N][N], dp[N][N];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int dfs(int x, int y){if(dp[x][y])return dp[x][y];dp[x][y] = 1;for(int i = 0; i < 4; i++){int xx = x + dx[i], yy = y + dy[i];if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] > a[x][y]){dp[x][y] = max(dp[x][y], dfs(xx, yy) + 1);}}return dp[x][y];
}
int main(){cin >> n >> m;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> a[i][j];}}int maxx = 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){maxx = max(maxx, dfs(i, j));}}cout << maxx << endl;return 0;
}

洛谷P1255爬楼梯：高精度加记忆化搜索

#include<iostream>
#include<vector> 
using namespace std;
int n;
vector<int>add(vector<int> &A, vector<int> &B){vector<int> C;int t = 0;for(int i = 0; i < A.size() | i < B.size(); i++){if(i < A.size())t += A[i];if(i < B.size())t += B[i];C.push_back(t % 10);t /= 10;}if(t)C.push_back(1);return C;
}
int main(){vector<int>A,B;cin >> n;if(n == 0 || n == 1){cout << 1 << endl;return 0;}vector<int> dp[n + 1];dp[0] = dp[1] = {1};for(int i = 2; i <= n; i++){dp[i] = add(dp[i - 1], dp[i - 2]);}for(int i = dp[n].size() - 1; i >= 0; i--)cout << dp[n][i];cout << endl; return 0;
}