阜阳企业做网站,广东建设银行网站,福州seo网络推广,浙江建设集团一、路径类
1. 字母收集 思路#xff1a; 1、预处理 对输入的字符矩阵我们按照要求将其转换为数字分数#xff0c;由于只能往下和往右走#xff0c;因此走到#xff08;i#xff0c;j#xff09;的位置要就是从#xff08;i - 1#xff0c; j#xff09;往下走#…一、路径类
1. 字母收集 思路 1、预处理 对输入的字符矩阵我们按照要求将其转换为数字分数由于只能往下和往右走因此走到ij的位置要就是从i - 1 j往下走或者是从(ij - 1)的位置往右走由于我们要使得路程遍历积分最多则应该从积分多的位置过来 2、状态表示 dp[i][j] 表示从[0, 0]出发到底[i, j]位置一共有多少分 3、状态转移方程 故ij位置的积分应该为dp[ i ][ j ] max(dp[ i - 1 ][ j ], dp[ i ][ j - 1 ]) dp[ i ][ j ]; 4、初始化 但是上面仅对于i 1 j 1成立对于第一行和第一列我们应该特殊处理利用前缀和的知识可以求得走到第一列的第i个位置最多能拿的积分以及走到第一行的第j个位置最多能拿的积分然后我们就可以按照dp[ i ][ j ] max(dp[ i - 1 ][ j ], dp[ i ][ j - 1 ]) dp[ i ][ j ]的方法遍历每个节点即可 #include iostream
using namespace std;const int N 1005;
int dp[N][N];int main() {int n, m;cin n m;char ch;for (int i 0; i n; i){for (int j 0; j m; j){cin ch;if (ch l) dp[i][j] 4;else if (ch o) dp[i][j] 3;else if (ch v) dp[i][j] 2;else if (ch e) dp[i][j] 1;else a[i][j] 0;}}for (int i 1; i n; i) dp[i][0] dp[i - 1][0] dp[i][0];
for (int j 1; j m; j) dp[0][j] dp[0][j - 1] dp[0][j]; for (int i 1; i n; i){for (int j 1; j m; j){dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) dp[i][j];}}cout dp[n - 1][m - 1] endl;return 0;
}2、[NOIP2002 普及组] 过河卒 分析 思路1、状态表示 dp[i][j] 表示从[0, 0]出发到底[i, j]位置一共有多少种方法2、状态转移方程 dp[ i ][ j ] dp[ i - 1 ][ j ] dp[i][j - 1] (i 0 j 0) 当走到马可以走的地方dp[ i ][ j ] 0;3、初始化 先创建一个 dp[ n 2 ][ m 2 ]然后让dp[ 0 ][ 1 ] 1 或者 dp[ 1 ][ 0 ] 1。注意这样初始化的时候x需要1,y也需要1.和dp表位置一一对应 #include iostream
#include vector
using namespace std;//int dp[1005][1005];
int main()
{int n, m, x, y;cin n m x y;vectorvectorlong long dp(n 2, vectorlong long(m 2));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;}else dp[i][j] dp[i - 1][j] dp[i][j - 1];}}cout dp[n 1][m 1] endl;return 0;
}
二、子序列和连续序列类
1. mari和shiny 线性 dp 在维护 i 位置之前⼀共有多少个 s sh 然后更新 shy 的个数。 1状态表示 s[i]字符串 str 中 [0, i] 区间内有多少个 s。 h[i]字符串 str 中 [0, i] 区间内有多少个 sh。 y[i]字符串 str 中 [0, i] 区间内有多少个 shy。 2状态转移方程 3空间优化 用三个变量来表示即可 s字符串 str 中 [0, n-1] 区间内有多少个 s h字符串 str 中 [0, n-1] 区间内有多少个 sh y字符串 str 中 [0, n-1] 区间内有多少个 shy 最后的遍历结束后y即我们需要的结果 #include iostream
#include string
using namespace std;
typedef long long ll;
int main()
{int n;string str;cin n str;ll s 0, h 0, y 0;for (int i 0; i n; i) {if (str[i] s) s;else if (str[i] h) h s;else if (str[i] y) y h;}cout y endl;return 0;
} 二维 dp 这道题目如果不是子序列而是要求连续序列的那就可以考虑用 KMP。 1dp[i][j] 含义 string tshy dp[i][j]以 i-1 为结尾的 str 子序列中出现以 j-1 为结尾的 t 的个数为 dp[i][j]。 2递推关系 str[i - 1] 与 t[j - 1]相等str[i - 1] 与 t[j - 1] 不相等 当 str[i - 1] 与 t[j - 1]相等时dp[i][j] 可以有两部分组成 一部分是用 str[i - 1] 来匹配那么个数为 dp[i - 1][j - 1]。即不需要考虑当前 str 子串和 t 子串的最后一位字母所以只需要 dp[i-1][j-1]。一部分是不用 str[i - 1] 来匹配个数为 dp[i - 1][j]。 为什么还要考虑不用 str[i - 1] 来匹配都相同了指定要匹配 例如 strshyy 和 tshy str[3] 和 t[2] 是相同的但是字符串 str 也可以不用 str[3] 来匹配即用 str[0]str[1]str[2] 组成的 shy。当然也可以用 str[3] 来匹配即str[0]str[1]str[3] 组成的 shy。 所以当 str[i - 1] 与 t[j - 1] 相等时dp[ i ][ j ] dp[ i - 1 ][ j - 1 ] dp[ i - 1 ][ j ]; 当 str[i - 1] 与 t[j - 1] 不相等时dp[i][j] 只有一部分组成不用 str[i - 1] 来匹配就是模拟在 str 中删除这个元素即dp[i - 1][j]所以递推公式为dp[ i ][ j ] dp[ i - 1 ][ j ]; 为什么只考虑 “不用 str[i - 1] 来匹配” 这种情况 不考虑 “不用 t[j - 1] 来匹配” 的情况呢 这里要明确我们求的是 str 中有多少个 t而不是求 t 中有多少个 str所以只考虑 str 中删除元素的情况即不用 str[i - 1] 来匹配 的情况。 3状态转移方程 dp[i][j]显然要从dp[i-1][?]递推而来。立即思考dp[i-1][j], dp[i-1][j-1]分别与dp[i][j]的关系。因为少一个字符自然而然从当前字符着手。考察si的第i个字符(表为s[i])和tj的第j个字符(表为t[j])的关系。 若s[i] ≠ t[j]那么s_i中的所有t_j子序列必不包含s[i]即s_i-1和s_i中tj的数量是一样的得到该情形的转移方程 dp[ i ][ j ] dp[ i -1 ][ j ] 若s[i] t[j]假设s_i中的所有t_j子序列中包含s[i]的有a个不包含的有b个。s_i中包含s[i]的子序列个数相当于s_i-1中t_j-1的个数不包含s[i]的子序列个数与上一种情况一样于是得到该情形的转移方程 a dp[ i -1 ][ j -1 ] b dp[ i-1 ][ j ] dp[ i ][ j ] a b dp[i-1][j-1] dp[i-1][j] 4遍历顺序 从上到下从左到右。 #include iostream
#include vectorusing namespace std;int main()
{int n;cin n;string str;cin str;string tshy;int mt.size();vectorvectorlong long dp(n1, vectorlong long(m1));for(int i0; in; i) dp[i][0]1;for(int i1; in; i){for(int j1; jm; j){if(str[i-1]t[j-1])dp[i][j]dp[i-1][j-1]dp[i-1][j];elsedp[i][j]dp[i-1][j];}}cout dp[n][m] endl;return 0;
}
2. 不同的子序列 该题于上题不一样的是上面给定了t的具体字符串而这里没有给定但是我们也需要用二维dp的方法来写。 1dp[i][j] 含义 s[ i ]的子序列中在t[ j ]出现的次数 s[ i ]表示s从下标 i 到末尾的子字符串。 t[ j ]表示t从下标 j 到末尾的子字符串。 2递推关系 分别令两个维度为0推测边界。dp[0][j]表示s_0中t_j的个数。s_0是空字符串只有当j0时才有dp[0][j] 1表示s子空串中有一个t子空串否则dp[0][j] 0因为一个空串不可能包含一个非空串。 dp[i][0]表示s_i中t0的个数。t_0是空字符串显然任何串包括空串都含有一个空子串。因此dp[i][0] 1。 注意到dp[i][0] 1实际上已经包含了dp[0][j] 1的情形。 3初始化 dp[i][0] 表示以 i-1 为结尾的 str 可以随便删除元素出现空字符串的个数。所以dp[i][0] 一定都是 1因为也就是把以 i-1 为结尾的 str删除所有元素出现空字符串的个数就是 1。dp[0][j] 表示空字符串 str 可以随便删除元素出现以 j-1 为结尾的字符串 t 的个数。所以dp[0][j] 一定都是 0因为 str 如论如何也变成不了 t。dp[0][0] 表示空字符串 str 可以删除 0 个元素变成空字符串 t。所以dp[0][0] 1。 4遍历顺序 从上到下从左到右。
int numDistinct(string s, string t) {int n s.size(), m t.size();if (n m) return 0;vectorvectorunsigned int dp(n 1, vectorunsigned int(m 1)); //注意是unsigned intfor (int i 0; i n; i) dp[i][0] 1;for (int i 1; i n; i) {for (int j 1; j m; j) {dp[i][j] dp[i - 1][j] (s[i - 1] t[j - 1] ? dp[i - 1][j - 1] : 0);}}return dp[n][m];
}
