• 动态规划PTA总结


    目录

    0动态规划

    1数字三角形

    1.1题目

    1.2代码

    1.3总结 

    2最长公共子序列

    2.1题目

    2.2代码

    2.3总结

    3单调递增最长子序列

    3.1题目

    3.2代码

    3.3总结

    4最大子段和

    4.1题目

    4.2代码

    4.3总结

    5最大子矩阵和

    5.1题目

    5.2代码

    5.3总结


    0动态规划

    最优子结构&&最值问题&&重叠子问题  --->  动态规划

    引用别人的文章

    1数字三角形

    1.1题目

    给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形
    的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下),使该路径经过的数字总和最大。

    输入格式:

    输入有n+1行:

    第 1 行是数字三角形的行数 n,1<=n<=100。

    接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。

    输出格式:

    输出最大路径的值。

    输入样例:

    在这里给出一组输入。例如:

    1. 5
    2. 7
    3. 3 8
    4. 8 1 0
    5. 2 7 4 4
    6. 4 5 2 6 5

    输出样例:

    在这里给出相应的输出。例如:

    30

    1.2代码

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. int maxMatrix[101][101];
    4. int main()
    5. {
    6. int n;
    7. cin >> n;
    8. // 读入数据
    9. for (int i = 1; i <= n; ++i)
    10. {
    11. for (int j = 1; j <= i; ++j)
    12. {
    13. int temp;
    14. cin >> temp;
    15. maxMatrix[i][j] = temp;
    16. }
    17. }
    18. // 动态规划
    19. for (int i = 2; i <= n; ++i)
    20. {
    21. for (int j = 1; j <= i; ++j)
    22. {
    23. if (j == 1)
    24. {
    25. maxMatrix[i][j] += maxMatrix[i - 1][j];
    26. }
    27. else if (j == i)
    28. {
    29. maxMatrix[i][j] += maxMatrix[i - 1][j - 1];
    30. }
    31. else
    32. {
    33. maxMatrix[i][j] += maxMatrix[i - 1][j - 1] > maxMatrix[i - 1][j] ? maxMatrix[i - 1][j - 1] : maxMatrix[i - 1][j];
    34. }
    35. }
    36. }
    37. // 找出最大值
    38. int max = maxMatrix[n][1];
    39. for (int i = 2; i <= n; ++i)
    40. {
    41. if (maxMatrix[n][i] > max)
    42. {
    43. max = maxMatrix[n][i];
    44. }
    45. }
    46. cout << max;
    47. return 0;
    48. }

    1.3总结 

    最优子结构:通过n-1行数字三角形中每条路径的数字总和可以得出n行数字三角形中每条路径的数字总和。

    最值问题:通过数字三角形中每条路径的数字总和,可以挑出数字总和最大的值。

    重叠子问题:样例中以第5行第一个数和第5行第二个数为末尾的路径的数字总和的计算都会用到以第4行第一个数为末尾的路径的数字总和。

    dp[i][j]二维数组:表示以第i行第j个数为末尾的路径的最大数字总和。

    遍历顺序:遍历的终点是把第n行的所有数字全部遍历完。

    代码思路

    1. 数字三角形行数存入n中,数字三角形的元素值存入maxMatrix中,maxMatrix同时也表示dp二维数组。
    2. 正向遍历,如果第i行第j个数是本行第一个数,那么maxMatrix[i][j]就等于maxMatrix[i][j]+maxMatrix[i-1][j];如果是本行最后一个数,那么maxMatrix[i][j]就等于maxMatrix[i][j]+maxMatrix[i-1][j-1];否则,maxMatrix[i][j]等于maxMatrix[i][j]加上maxMatrix[i-1][j-1]和maxMatrix[i-1][j]中更大的数。
    3. 遍历第n行的maxMatrix,找出最大值。

    2最长公共子序列

    2.1题目

    现在给你两个由AGCT四个字母构成的字符串,请你求出两个DNA序列的最长公共子序列。

    输入格式:

    两行,每行一个字符串,分别表示一个DNA序列(每个字符串长度不超过1000)。

    输出格式:

    一个数,最长公共子序列元素的个数。

    输入样例:

    在这里给出一组输入。例如:

    1. AGCT
    2. ATT

    输出样例:

    在这里给出相应的输出。例如:

    2

    2.2代码

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. int maxLen[1001][1001];
    4. int main()
    5. {
    6. string s1, s2;
    7. cin >> s1 >> s2;
    8. for (int i = 1; i <= s1.length(); ++i)
    9. {
    10. for (int j = 1; j <= s2.length(); ++j)
    11. {
    12. if (s1[i] == s2[j])
    13. {
    14. maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
    15. }
    16. else
    17. {
    18. maxLen[i][j] = maxLen[i - 1][j] > maxLen[i][j - 1] ? maxLen[i - 1][j] : maxLen[i][j - 1];
    19. }
    20. }
    21. }
    22. cout << maxLen[s1.length()][s2.length()];
    23. return 0;
    24. }

    2.3总结

    最优子结构:通过s1[0-i]和s2[0-j]的最长公共子序列长度可以得出s1[0-(i+1)]和s2[0-(j+1)]的最长公共子序列长度。

    最值问题:两个字符串的最长公共子序列就是dp[s1.length][s2.length]的值。

    重叠子问题:dp[i][j]会在求dp[i+1][j+1]和dpdp[i+1][j]和dp[i][j+1]时用到。

    dp[i][j]二维数据:表示s1[0~i]和s2[0~j]的最长公共子序列长度。

    遍历顺序:遍历的终点是dp[s1.length][s2.length]。

    代码思路

    1. s1和s2用来存储两个字符串,maxLen二维数组表示dp二维数组。
    2. 正向遍历,如果s1[i]==s2[j],那么maxLen[i][j]=maxLen[i-1][j-1]+1;否则,maxLen[i][j]=maxLen[i][j-1]和maxLen[i-1][j]的较大值。
    3. maxLen[s1.length][s2.length]即为两个字符串的最长公共子序列长度。

    注意

    公共子序列和公共子串:公共子序列可以不连续,公共子串必须连续。 

    3单调递增最长子序列

    3.1题目

    设计一个O(n2)时间的算法,找出由n个数组成的序列的最长单调递增子序列。

    输入格式:

    输入有两行:
    第一行:n,代表要输入的数列的个数
    第二行:n个数,数字之间用空格格开

    输出格式:

    最长单调递增子序列的长度

    输入样例:

    在这里给出一组输入。例如:

    1. 5
    2. 1 3 5 2 9

    输出样例:

    在这里给出相应的输出。例如:

    4

    3.2代码

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. int main()
    4. {
    5. int n;
    6. cin >> n;
    7. int array[100001];
    8. for (int i = 0; i < n; ++i)
    9. {
    10. cin >> array[i];
    11. }
    12. int maxLen[100001];
    13. for (int i = 0; i < n; ++i)
    14. {
    15. maxLen[i] = 1;
    16. }
    17. int max = maxLen[0];
    18. for (int i = 1; i < n; ++i)
    19. {
    20. for (int j = 0; j < i; ++j)
    21. {
    22. if (array[i] > array[j] && maxLen[i] >= maxLen[j])
    23. {
    24. maxLen[i] = maxLen[j] + 1;
    25. max = maxLen[i] > max ? maxLen[i] : max;
    26. }
    27. }
    28. }
    29. cout << max;
    30. return 0;
    31. }

    3.3总结

    最优子结构:通过以第i个数结尾的单调递增子序列的长度可以得出以第j个数结尾的单调递增子序列的长度(j>i,第j个数是第一个比第i个数大的数)。

    最值问题:比较n个最长单调递增子序列的长度,挑出最长的。

    重叠子问题:第i个数结尾的单调递增子序列的长度会被多次用到。

    dp[i]一维数组:用来表示以第i个数字结尾的最长单调递增子序列的长度。

    遍历顺序: 遍历的终点是把所有i遍历完。

    代码思路: 

    1. n存入序列长度,array一维数组存放序列元素,maxLen一维数组表示dp数组,初始化为1(元素本身长度为1)。
    2. max表示当前最长单调递增子序列长度。遍历这n个序列元素,对于每一个元素,都要遍历其前面的每一个元素,找出前面的小于自己的元素中最长单调子序列的长度,然后加1,赋给自己。
    3. 输出max。

    4最大子段和

    4.1题目

    给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时,定义子段和为0。

    要求算法的时间复杂度为O(n)。

    输入格式:

    输入有两行:

    第一行是n值(1<=n<=10000);

    第二行是n个整数。

    输出格式:

    输出最大子段和。

    输入样例:

    在这里给出一组输入。例如:

    1. 6
    2. -2 11 -4 13 -5 -2

    输出样例:

    在这里给出相应的输出。例如:

    20

    4.2代码

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. int n;
    4. int maxSum[10001];
    5. int main()
    6. {
    7. cin >> n;
    8. int array[10001];
    9. int max = 0;
    10. for (int i = 1; i <= n; ++i)
    11. {
    12. cin >> array[i];
    13. maxSum[i] = array[i] + (maxSum[i - 1] > 0 ? maxSum[i - 1] : 0);
    14. max = maxSum[i] > max ? maxSum[i] : max;
    15. }
    16. cout << max;
    17. return 0;
    18. }

    4.3总结

    最优子结构:通过以a[i]结尾的最大子段和可以得出以a[i+1]结尾的最大子段和。

    最值问题:在所有的以a[i]结尾的最大子段和中找出最大值。

    重叠子问题:求dp的过程中要用到,最终求最值也要用到。

    dp[i]一维数组:表示以a[i]结尾的最大子段和。

    遍历顺序: 遍历的终点是把所有的以a[i]结尾的最大子段和都求出来。

    代码思路: 

    1. n存储序列元素个数,array数组存储序列元素,maxSum表示dp。
    2. 正向遍历,如果maxSum[i]大于0,那么maxSum[i+1]=maxSum[i]+array[i];否则,maxSum[i]=array[i]。max用来表示当前的最大子段和。
    3. 输出最大子段和。

    5最大子矩阵和

    5.1题目

    最大子矩阵和问题。给定m行n列的整数矩阵A,求矩阵A的一个子矩阵,使其元素之和最大。

    输入格式:

    第一行输入矩阵行数m和列数n(1≤m≤100,1≤n≤100),再依次输入m×n个整数。

    输出格式:

    输出第一行为最大子矩阵各元素之和,第二行为子矩阵在整个矩阵中行序号范围与列序号范围。

    输入样例1:

    1. 5 6
    2. 60 3 -65 -92 32 -70
    3. -41 14 -38 54 2 29
    4. 69 88 54 -77 -46 -49
    5. 97 -32 44 29 60 64
    6. 49 -48 -96 59 -52 25

    输出样例1:

    输出第一行321表示子矩阵各元素之和,输出第二行2 4 1 6表示子矩阵的行序号从2到4,列序号从1到6

    1. 321
    2. 2 4 1 6

    5.2代码

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. int m, n;
    4. int *getMaxSum(int *array)
    5. {
    6. int dp[102][2] = {{0, 0}};
    7. int max = array[0];
    8. int begin = 1, end = 1;
    9. for (int i = 1; i <= n; ++i)
    10. {
    11. if (dp[i - 1][0] > 0)
    12. {
    13. dp[i][0] = dp[i - 1][0] + array[i - 1];
    14. dp[i][1] = dp[i - 1][1] + 1;
    15. }
    16. else
    17. {
    18. dp[i][0] = array[i - 1];
    19. dp[i][1] = 1;
    20. }
    21. if (dp[i][0] > max)
    22. {
    23. max = dp[i][0];
    24. end = i;
    25. begin = i - dp[i][1] + 1;
    26. }
    27. }
    28. // for (int i = 1; i <= n; ++i)
    29. // {
    30. // cout << endl;
    31. // cout << "dp[" << i << "][0] = " << dp[i][0] << " ";
    32. // }
    33. // cout << endl;
    34. int *result = new int[3];
    35. result[0] = max;
    36. result[1] = begin;
    37. result[2] = end;
    38. return result;
    39. }
    40. int *getResultArray(int array[][101], int hangShu)
    41. {
    42. int *result = new int[102];
    43. for (int i = 0; i < n; ++i)
    44. {
    45. result[i] = 0;
    46. }
    47. for (int i = 0; i < hangShu; ++i)
    48. {
    49. for (int j = 0; j < n; ++j)
    50. {
    51. result[j] += array[i][j];
    52. }
    53. }
    54. return result;
    55. }
    56. int main()
    57. {
    58. int matrix[101][101];
    59. cin >> m >> n;
    60. for (int i = 0; i < m; i++)
    61. {
    62. for (int j = 0; j < n; j++)
    63. {
    64. cin >> matrix[i][j];
    65. }
    66. }
    67. int *result = getMaxSum(matrix[0]);
    68. int max = result[0];
    69. int hangBegin = 1, hangEnd = 1, lieBegin = result[1], lieEnd = result[2];
    70. for (int i = 1; i <= m; ++i)
    71. {
    72. for (int j = 0; j <= m - i; ++j)
    73. {
    74. int *temp = getMaxSum(getResultArray(matrix + j, i));
    75. if (temp[0] > max)
    76. {
    77. // cout << "yes" << endl;
    78. max = temp[0];
    79. hangBegin = j + 1;
    80. hangEnd = hangBegin + i - 1;
    81. lieBegin = temp[1];
    82. lieEnd = temp[2];
    83. }
    84. }
    85. }
    86. cout << max << endl;
    87. cout << hangBegin << " " << hangEnd << " " << lieBegin << " " << lieEnd;
    88. return 0;
    89. }

    5.3总结

    代码思路: 

    1. m存储行数,n存储列数,matrix存储矩阵元素。
    2. 处理行宽为1的矩阵(序列),记录最大值;处理行宽为2的矩阵(两个一维序列的对应位相加->一个一维序列),记录最大值......
    3. 输出最大值。
  • 相关阅读:
    Tomcat10+Spring6报错
    大数据安全 测试
    2023年之我拿起“java“ java基础进阶1
    极客日报:网易回应旗下游戏集体崩溃:用干冰修好了服务器;GitHub更换CEO,由产品主管接手;Nginx 1.21.4发布
    多数互联网人对2021年终奖不抱期待
    ODrive移植keil(四)—— PWM触发ADC采样
    java基于微信小程序的社区心理健康咨询辅导服务系统 uniapp 小程序
    lunatic亚毫秒 Web 框架的LiveView实时视图
    ASP.NET Core 8 在 Windows 上各种部署模型的性能测试
    Sentinel 熔断与限流
  • 原文地址:https://blog.csdn.net/peanutpeanuta/article/details/128141737