数字三角形

const int N = 510, INF = 0x3f3f3f3f;
int n, m[N][N], dp[N][N];
int main()
{// ------- 0 based index --------cin >> n;for(int i = 0; i < n; ++i)for(int j = 0; j <= i; ++j)cin >> m[i][j];// fill(dp[0], dp[0] + N * N, -INF);    // 避免一些不相关位置的初始值干扰状态更新for(int i = 0; i < N; ++i)for(int j = 0; j < N; ++j)dp[i][j] = -INF;dp[0][0] = m[0][0];for(int i = 1; i < n; ++i){for(int j = 0; j <= i; ++j){if(j == 0)  					// 因为是 0 based index，所以左边界要手动判断                    dp[i][j] = dp[i - 1][j] + m[i][j];// else if(j == i)              // 若没有初始化-INF避免干扰，则需手动判断边界//     dp[i][j] = dp[i - 1][j - 1] + m[i][j];elsedp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + m[i][j];}}// Test code// for(int i = 0; i < n; ++i)// {//     for(int j = 0; j <= i; ++j)//         cout << dp[i][j] << " ";//     cout << endl;// }int ret = -0x3f3f3f3f;for(int j = 0; j < n; ++j)ret = max(ret, dp[n - 1][j]);cout << ret;// ------- 1 based index --------// cin >> n;// for(int i = 1; i <= n; ++i)//     for(int j = 1; j <= i; ++j)//         cin >> m[i][j];// // fill(dp[0], dp[0] + N * N, -INF);    // 避免一些不相关位置的初始值干扰状态更新// for(int i = 0; i < N; ++i)//     for(int j = 0; j < N; ++j)//         dp[i][j] = -INF;// dp[1][1] = m[1][1];// for(int i = 2; i <= n; ++i)// {//     for(int j = 1; j <= i; ++j)//     {//         // if(j == 0)                      // 若没有初始化避免干扰，则需手动判断边界//         //     dp[i][j] = dp[i - 1][j] + m[i][j];//         // else if(j == i)//         //     dp[i][j] = dp[i - 1][j - 1] + m[i][j];//         // else//             dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + m[i][j];//     }// }// // for(int i = 1; i <= n; ++i)// // {// //     for(int j = 1; j <= i; ++j)// //         cout << dp[i][j] << " ";// //     cout << endl;// // }// int ret = -0x3f3f3f3f;// for(int j = 1; j <= n; ++j)//     ret = max(ret, dp[n][j]);// cout << ret;return 0;
}

最长上升子序列

const int N = 1010, INF = 0x3f3f3f3f;
int n, a[N], dp[N];
int main()
{cin >> n;for(int i = 0; i < n; ++i)cin >> a[i];fill(dp, dp + N, 1);int ret = 1;for(int i = 1; i < n; ++i){for(int j = 0; j < i; ++j){if(a[i] > a[j])dp[i] = max(dp[i], dp[j] + 1);}ret = max(ret, dp[i]);}// for(int i = 0; i < n; ++i)//     cout << dp[i] << " ";// cout << endl;cout << ret;return 0;
}

最长公共子序列

• dp[i][j]：A中前 i 位的所有子序列(含i或不含i)，B中前 j 位的所有子序列(含j或不含j)，中的最长公共子序列的长度
• 根据 i j 位置的情乱进行讨论
• 针对不同情况中的重复部分的处理，这里是取最大值所以不影响

const int N = 1010;
int n, m, dp[N][N];
string s1, s2;int main()
{cin >> n >> m;cin >> s1 >> s2;s1 = " " + s1;s2 = " " + s2;for(int i = 1; i <= n; ++i){for(int j = 1; j <= m; ++j){if(s1[i] == s2[j])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);}}cout << dp[n][m];return 0;
}

最短编辑距离

• dp[i][j]：将A中1-i 改为B中1-j 的所有方法中，编辑最少的次数
• 考虑最后一个位置，即第 i 位置 和 第 j 位置
• 初始化： dp[i][0] = dp[0][i] = i;

const int N = 1010;
int n, m, dp[N][N];
string s1, s2;int main()
{cin >> n >> s1;cin >> m >> s2;s1 = " " + s1;s2 = " " + s2;for(int i = 1; i < N; ++i)dp[i][0] = dp[0][i] = i;for(int i = 1; i <= n; ++i){for(int j = 1; j <= m; ++j){dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;if(s1[i] != s2[j])dp[i][j] = min(dp[i][j], dp[i - 1][j -1] + 1);elsedp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);}}cout << dp[n][m];return 0;
}

编辑距离

const int N = 1010, LEN = 15;
int n, m, dp[LEN][LEN];
string s[N];
int edit_step(string s1, string s2)
{int n1 = s1.size(), n2 = s2.size();// cout << s1 << " " << s2 << endl;for(int i = 1; i <= n1; ++i)dp[i][0] = i;for(int i = 1; i <= n2; ++i)dp[0][i] = i;for(int i = 1; i <= n1; ++i){for(int j = 1; j <= n2; ++j){dp[i][j] = min(dp[i - 1][j], dp[i][j -1]) + 1;if(s1[i - 1] != s2[j - 1])dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);elsedp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);}}return dp[n1][n2];
}int main()
{cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> s[i];while(m--){string tmp;int bar;cin >> tmp >> bar;int cnt = 0;for(int i = 1; i <= n; ++i)if(edit_step(tmp, s[i]) <= bar)cnt++;cout << cnt << endl;}return 0;
}