基础动态规划题目基础动态规划题目

目录
题目1： P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles
 代码示例：
题目2： Common Subsequence
代码示例
题目3 ：最长上升子序列
最长不下降子序列
最长上升子序列oj答案
题目1： P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles - 洛谷 | 盘算机科学教育新生态 (luogu.com.cn)

https://www.luogu.com.cn/problem/P1216

 代码示例：

1. // c++ 代码示例
2. #include <algorithm>
3. #include <iostream>
5. using namespace std ;
7. int n,a[1005][1005],f[1005][1005] ;
9. int dfs(int x, int y)
10. {
11.     if (x == n) return a[x][y] ;
12.     if (f[x][y] != -1) return f[x][y] ;
13.     return f[x][y] = max(dfs(x + 1, y), dfs(x + 1, y + 1)) + a[x][y] ;
14. }
16. int main()
17. {
18.     int n ;
19.     cin >> n ;
20.     for (int i = 1 ; i <= n ; i++)
21.     {
22.         for (int j = 1 ; j <= i ; j++)
23.         {
24.             cin >> a[i][j] ;
25.         }
26.     }
27.     for (int i = 1 ; i <= n ; i++)
28.     {
29.         for (int j = 1 ; j <= i ; j++)
30.         {
31.             f[i][j] = -1 ;
32.         }
33.     }
34.     cout << dfs(1, 1) ;
35.     return 0 ;
36. }

复制代码

1. // c++ 代码示例
3. #include <algorithm>
4. #include <iostream>
5. using namespace std ;
7. long long n, a[1005][1005] ;
8. int main()
9. {
10.     cin >> n ;
11.     for (int i = 1 ; i <= n ; i++)
12.     {
13.         for (int j = 1 ; j <= i ; j++)
14.         {
15.             cin >> a[i][j] ;
16.         }
17.     }
18.     for (int i = n ; i >= 1 ; i--)
19.     {
20.         for (int j = 1 ; j <= i ; j++)
21.         {
22.             a[i][j] = a[i][j] + max(a[i + 1][j], a[i + 1][j + 1]);        
23.             
24.         }
25.     }
26.     cout << a[1][1] ;
27.     return 0 ;
28.    
29. }

复制代码

 

1. // c++ 代码示例
3. #include <algorithm>
4. #include <iostream>
5. #include <cstdlib>
6. #include <cstring>
7. #include <cstdio>
8. #include <string>
9. using namespace std;
11. #define rint register int
12. inline void read(int &x)
13. {
14.     x = 0;
15.     int w = 1;
16.     char ch = getchar();
17.     while (!isdigit(ch) && ch != '-')
18.     {
19.         ch = getchar();
20.     }
21.     if (ch == '-')
22.     {
23.         w = -1;
24.         ch = getchar();
25.     }
26.     while (isdigit(ch))
27.     {
28.         x = (x << 3) + (x << 1) + (ch ^ '0');
29.         ch = getchar();
30.     }
31.     x = x * w;
32. }
34. const int maxn = 1000 + 10;
36. int n, a[maxn][maxn], ans;
38. int main()
39. {
40.     read(n);
41.     for (rint i = 1; i <= n; i++)
42.     {
43.         for (rint j = 1; j <= i; j++)
44.         {
45.             read(a[i][j]);
46.             if (i == 1 && j == 1)
47.             {
48.                 // The top of the triangle
49.                 continue;
50.             }
51.             if (j == 1)
52.             {
53.                 // Left boundary
54.                 a[i][j] += a[i - 1][j];
55.             }
56.             else if (j == i)
57.             {
58.                 // Right boundary
59.                 a[i][j] += a[i - 1][j - 1];
60.             }
61.             else
62.             {
63.                 // Middle elements
64.                 a[i][j] += max(a[i - 1][j - 1], a[i - 1][j]);
65.             }
66.             ans = max(ans, a[i][j]);
67.         }
68.     }
69.     cout << ans << endl;
70.     return 0;
71. }

复制代码

题目2： Common Subsequence

Common Subsequence - HDU 1159 - Virtual Judge (vjudge.net)

https://vjudge.net/problem/HDU-1159
代码示例

1. // c++ 代码示例
2. int a[MAXN], b[MAXN], f[MAXN][MAXN] ;
4. int dp()
5. {
6.     for (int i = 1 ; i <= n ; i++)
7.     {
8.         for (int j = 1 ; j <= m ; j++)
9.         {
10.             if (a[i - 1] == b[j - 1])
11.             {
12.                 f[i][j] = f[i - 1][j - 1] + 1 ;
13.             }
14.             else
15.             {
16.                 f[i][j] = std::max(f[i - 1][j], f[i][j - 1]) ;
17.             }
18.         }
19.     }
20.     return f[n][m] ;
21. }

复制代码

1. // c++ 代码示例
3. #include <cmath>
4. #include <iostream>
5. #include <cstdio>
6. #include <cstdlib>
7. #include <cstring>
8. #include <algorithm>
10. using namespace std;
12. char a[1001], b[1001];
13. int dp[1001][1001], len1, len2;
15. void lcs(int i,int j)
16. {
17.     for(i=1; i<=len1; i++)
18.     {
19.         for(j=1; j<=len2; j++)
20.         {
21.             if(a[i-1] == b[j-1])
22.                 dp[i][j] = dp[i-1][j-1] + 1;
23.             else if(dp[i-1][j] > dp[i][j-1])
24.                 dp[i][j] = dp[i-1][j];
25.             else
26.                 dp[i][j] = dp[i][j-1];
27.         }
28.     }
29. }
31. int main()
32. {
33.     while(~scanf(" %s",a))
34.     {
35.         scanf(" %s", b);
36.         memset(dp, 0, sizeof(dp));
37.         len1 = strlen(a);
38.         len2 = strlen(b);
39.         lcs(len1, len2);
40.         printf("%d\n", dp[len1][len2]);
41.     }
42.     return 0;
43. }

复制代码

题目3 ：最长上升子序列

信息学奥赛一本通（C++版）在线评测体系 (ssoier.cn)

http://ybt.ssoier.cn:8088/problem_show.php?pid=1281
最长不下降子序列

1. //c++代码示例
2. # include <iostream>
3. # include <cstdio>
4. using namespace std ;
5. int n ;
6. int a[1001] ;
7. int f[1001] ;
8. int mx = -1 ;
9. int main()
10. {
11.     scanf("%d", &n) ;
12.     for (int i = 1 ; i <= n ; i++)
13.     {
14.         scanf("%d", &a[i]) ;
15.         f[i] = 1 ;
16.     }
17.     for (int i = 2 ; i <= n ; i++)
18.     {
19.         for (int j = i - 1 ; j >= 1 ; j--)
20.         {
21.             if (a[i] >= a[j])
22.             {
23.                 f[i] = max(f[i], f[j] + 1) ;
24.             }
25.         }
26.     }
27.     for (int i = 1 ; i <= n ; i++)
28.     {
29.         mx = max(mx, f[i]) ;
30.     }
31.     printf("%d", mx) ;
32.     return 0 ;
33.    
34. }

复制代码

1. //c++代码示例
2. # include <iostream>
3. # include <cstdio>
4. using namespace std ;
5. int n ;
6. int a[1001] ;
7. int f[1001] ;
8. int mx = -1 ;
9. int main()
10. {
11.     scanf("%d", &n) ;
12.     for (int i = 1 ; i <= n ; i++)
13.     {
14.         scanf("%d", &a[i]) ;
15.         f[i] = 1 ;
16.     }
17.     for (int i = n - 1 ; i >= 1 ; i--)
18.     {
19.         for (int j = i + 1 ; j <= n ; j++)
20.         {
21.             if (a[i] <= a[j])
22.             {
23.                 f[i] = max(f[i], f[j] + 1) ;
24.             }
25.         }
26.     }
27.     for (int i = 1 ; i <= n ; i++)
28.     {
29.         mx = max(mx, f[i]) ;
30.     }
31.     printf("%d", mx) ;
32.     return 0 ;
33.    
34. }

复制代码

最长上升子序列oj答案

1. //c++代码示例
2. # include <iostream>
3. # include <cstdio>
4. using namespace std ;
5. int n ;
6. int a[1001] ;
7. int f[1001] ;
8. int mx = -1 ;
9. int main()
10. {
11.     scanf("%d", &n) ;
12.     for (int i = 1 ; i <= n ; i++)
13.     {
14.         scanf("%d", &a[i]) ;
15.         f[i] = 1 ;
16.     }
17.     for (int i = n - 1 ; i >= 1 ; i--)
18.     {
19.         for (int j = i + 1 ; j <= n ; j++)
20.         {
21.             if (a[i] < a[j])
22.             {
23.                 f[i] = max(f[i], f[j] + 1) ;
24.             }
25.         }
26.     }
27.     for (int i = 1 ; i <= n ; i++)
28.     {
29.         mx = max(mx, f[i]) ;
30.     }
31.     printf("%d", mx) ;
32.     return 0 ;
33.    
34. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。