devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

动态规划经典例题

作者：Cpp五条 | 2024-05-30 06:08:03

赞

踩

动态规划经典例题

哈希

1. 数组中出现次数超过一半的数字

描述

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：�≤50000n≤50000，数组中元素的值 0≤���≤100000≤val≤10000

要求：空间复杂度：�(1)O(1)，时间复杂度 �(�)O(n)

输入描述：

保证数组输入非空，且保证有解

示例1

输入：

[1,2,3,2,2,2,5,4,2]

复制返回值：

2

复制

示例2

输入：

[3,3,3,3,2,2,2]

复制返回值：

3
  1. #include <stdlib.h>
  2. int arr[10001] = {0};
  3. int max = 0;
  4. int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
  5.     // write code here
  6.     for (int i = 0; i < numbersLen; i++) {
  7.         arr[numbers[i]]++;
  8.     }
  9.     for (int i = 0; i < numbersLen; i++) {
  10.         if (arr[numbers[i]] > numbersLen / 2) {
  11.             return numbers[i];
  12.         }
  13.     }
  14.     return 0;
  15. }

2.  数组中只出现一次的两个数字

描述

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

数据范围：数组长度 2≤�≤10002≤n≤1000，数组中每个数的大小 0<���≤10000000<val≤1000000
要求：空间复杂度 �(1)O(1)，时间复杂度 �(�)O(n)

提示：输出时按非降序排列。

示例1

输入：

[1,4,1,6]

复制返回值：

[4,6]

复制说明：

返回的结果中较小的数排在前面

示例2

输入：

[1,2,3,3,2,9]

复制返回值：

[1,9]
  1. int* FindNumsAppearOnce(int* nums, int numsLen, int* returnSize ) {
  2.     // write code here
  3.     int hash[1000000] = {0};
  4.     int values[2] = {0};
  5.     int count = 0;
  6.     for (int i = 0; i < numsLen; i++) {
  7.         hash[nums[i]]++;
  8.     }
  9.     for (int i = 0; i < numsLen; i++) {
  10.         if (hash[nums[i]] == 1) {
  11.             values[count++] = nums[i];
  12.         }
  13.     }
  14.     if (values[0] > values[1]) {
  15.         int tem = values[0];
  16.         values[0] = values[1];
  17.         values[1] = tem;
  18.     }
  19.     *returnSize = 2;
  20.     return values;
  21. }

 3. 缺失的第一个正整数

描述

给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数

进阶： 空间复杂度 �(1)O(1)，时间复杂度 �(�)O(n)

数据范围:

−231≤����[�]≤231−1−231≤nums[i]≤231−1

0≤���(����)≤5∗1050≤len(nums)≤5∗105

示例1

输入：

[1,0,2]

复制返回值：

3

复制

示例2

输入：

[-2,3,4,1,5]

复制返回值：

2
  1. int minNumberDisappeared(int* nums, int numsLen ) {
  2.     // write code here
  3.     int value = 0;
  4.     long arr[500000] = {0};
  5.     for (int i = 0; i < numsLen; i++) {
  6.         if (nums[i] > 0)
  7.         arr[nums[i]] = nums[i];
  8.     }
  9.     for (int i = 1; i < 500000; i++) {
  10.         if (arr[i] != i) {
  11.             value = i;
  12.             break;
  13.         }
  14.     }
  15.     return value;
  16. }

 动态规划

1. 跳台阶

描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：1≤�≤401≤n≤40

要求：时间复杂度：�(�)O(n) ，空间复杂度： �(1)O(1)

示例1

输入：

2

复制返回值：

2

复制说明：

青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2

示例2

输入：

7

复制返回值：

21

  1. int jumpFloor(int number ) {
  2.     // write code here
  3.     int value[number + 1];
  4.     value[1] = 1;
  5.     value[2] = 2;
  6.     for (int i = 3; i <= number; i++) {
  7.         value[i] = value[i - 1] + value[i - 2];
  8.     }
  9.     return value[number];
  10. }

 2. 最小花费爬楼梯

描述

给定一个整数数组 ���� cost  ，其中 ����[�] cost[i]  是从楼梯第� i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 

请你计算并返回达到楼梯顶部的最低花费。

数据范围：数组长度满足 1≤�≤105 1≤n≤105  ，数组中的值满足 1≤�����≤104 1≤costi​≤104 

示例1

输入：

[2,5,20]

复制返回值：

5

复制说明：

你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5   
  1. int minCostClimbingStairs(int* cost, int costLen ) {
  2.     // write code here
  3.     int dp[100000] = {0};
  4.     if (costLen == 1) {
  5.         return cost[0];
  6.     } else if (costLen == 2) {
  7.         return cost[0] < cost[1] ? cost[0] : cost[1];
  8.     } else {
  9.         for (int i = 2; i <= costLen; i++) {
  10.             //当前位置无非两种情况：
  11.             //1.由前一个阶梯跨来
  12.             //2.由前两个阶梯跨来
  13.             int x = dp[i - 1] + cost[i - 1];
  14.             int y = dp[i - 2] + cost[i - 2];
  15.             //选取花费最少的情况
  16.             dp[i] = x < y ? x : y;
  17.         }
  18.     }
  19.     return dp[costLen];
  20. }

 3. 最长公共子串

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。 

数据范围： 1≤∣���1∣,∣���2∣≤50001≤∣str1∣,∣str2∣≤5000
要求： 空间复杂度 �(�2)O(n2)，时间复杂度 �(�2)O(n2)

示例1

输入：

"1AB2345CD","12345EF"

复制返回值：

"2345"

  1. #include <string.h>
  2. char* LCS(char* str1, char* str2 ) {
  3.     // write code here
  4.     int cnt = 0;
  5.     int cntmax = 0;
  6.     char temres[5001] = {0};
  7.     char res[5001] = {0};
  8.     for (int i = 0; i < strlen(str1); i++) {
  9.         for (int j = 0; j < strlen(str2); j++) {
  10.             cnt = 0;
  11.             if (str1[i] == str2[j]) {
  12.                 int temi = i;
  13.                 int temj = j;
  14.                 while (str1[temi] == str2[temj] && temi < strlen(str1) && temj < strlen(str2)) {
  15.                     temres[cnt++] = str1[temi];
  16.                     temi++;
  17.                     temj++;
  18.                 }
  19.                 if (cnt > cntmax) {
  20.                     for (int k = 0; k < cnt; k++) {
  21.                         res[k] = temres[k];
  22.                     }
  23.                     cntmax =cnt;
  24.                 }
  25.              }
  26.         }
  27.     }
  28.     return res;
  29. }

 4. 不同路径的数目(一)

描述

一个机器人在m×n大小的地图的左上角（起点）。

机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

备注：m和n小于等于100,并保证计算结果在int范围内

数据范围：0<�,�≤1000<n,m≤100，保证计算结果在32位整型范围内

要求：空间复杂度 �(��)O(nm)，时间复杂度 �(��)O(nm)

进阶：空间复杂度 �(1)O(1)，时间复杂度 �(���(�,�))O(min(n,m))

示例1

输入：

2,1

复制返回值：

1

复制

示例2

输入：

2,2

复制返回值：

2
  1. int uniquePaths(int m, int n ) {
  2.     // write code here
  3.     int dp[100][100] = {0};
  4.     for (int i = 0; i < m; i++) {
  5.         dp[i][0] = 1;
  6.     }
  7.     for (int i = 0; i < n; i++) {
  8.         dp[0][i] = 1;
  9.     }
  10.     for (int i = 1; i < m; i++) {
  11.         for (int j = 1; j < n; j++) {
  12.             dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  13.         }
  14.     }
  15.     return dp[m - 1][n - 1];
  16. }

 5. 矩阵的最小路径和

描述

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

数据范围: 1≤�,�≤5001≤n,m≤500，矩阵中任意值都满足 0≤��,�≤1000≤ai,j​≤100

要求：时间复杂度 �(��)O(nm)

例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，

所选择的最小累加和路径如下图所示：

示例1

输入：

[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]

复制返回值：

12

复制

示例2

输入：

[[1,2,3],[1,2,3]]

复制返回值：

7
  1. #include <math.h>
  2. #include <string.h>
  3. int mymin(int a, int b) {
  4.     return a < b ? a : b;
  5. }
  6.  
  7. int minPathSum(int** matrix, int matrixRowLen, int* matrixColLen ) {
  8.     // write code here
  9.     int row = matrixRowLen;
  10.     int col = *matrixColLen;
  11.     int dp[row][col];
  12.     memset(dp, 0, 4 * row * col);
  13.     dp[0][0] = matrix[0][0];
  14.     for (int i = 1; i < row; i++) {
  15.         dp[i][0] = dp[i - 1][0] + matrix[i][0];
  16.     }
  17.     for (int i = 1; i < col; i++) {
  18.         dp[0][i] = dp[0][i - 1] + matrix[0][i];
  19.     }
  20.     for (int i = 1; i < row; i++) {
  21.         for (int j = 1; j < col; j++) {
  22.             int m = mymin(dp[i - 1][j], dp[i][j - 1]);
  23.             dp[i][j] = matrix[i][j] + m;
  24.         }
  25.     }
  26.     return dp[row - 1][col - 1];
  27. }

 6. 把数字翻译成字符串

描述

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。

现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 0<�≤900<n≤90

进阶：空间复杂度 �(�)O(n)，时间复杂度 �(�)O(n)

示例1

输入：

"12"

复制返回值：

2

复制说明：

2种可能的译码结果（”ab” 或”l”）

示例2

输入：

"31717126241541717"

复制返回值：

192

复制说明：

192种可能的译码结果  
  1. #include <string.h>
  2. int solve(char* nums ) {
  3.     // write code here
  4.     int len = strlen(nums);
  5.     int arr[len];
  6.     for (int i = 0; i < len; i++) {
  7.         arr[i] = nums[i] - '0';
  8.     }
  9.  
  10.     if (arr[0] == 0) {
  11.         return 0;
  12.     } 
  13.     if (len == 2 && (arr[0] == 1 && arr[1] == 0 || arr[0] == 2 && arr[1] == 0)) {
  14.         return 1;
  15.     }
  16.     for (int i = 1; i < len; i++) {
  17.         if (arr[i] == 0) {
  18.             if (arr[i - 1] != 1 && arr[i - 1] != 2) {
  19.                 return 0;
  20.             }
  21.         }
  22.     }
  23.     int dp[len + 1];
  24.     for (int i = 0; i <= len; i++) {
  25.         dp[i] = 1;
  26.     }
  27.     for (int i = 2; i <= len; i++) {
  28.         //11-19 21-26两种解码方式
  29.         int x = 10 * arr[i - 2] + arr[i - 1];
  30.         if (11 <= x && x <= 19 || 21 <= x && x <= 26) {
  31.             dp[i] = dp[i - 1] + dp[i - 2];
  32.         } else {
  33.             dp[i] = dp[i - 1];
  34.         }
  35.     }
  36.     return dp[len];
  37. }

 7. 兑换零钱(一)

描述

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。

如果无解，请返回-1.

数据范围：数组大小满足 0≤�≤100000≤n≤10000 ， 数组中每个数字都满足 0<���≤100000<val≤10000，0≤���≤50000≤aim≤5000

要求：时间复杂度 �(�×���)O(n×aim) ，空间复杂度 �(���)O(aim)。

示例1

输入：

[5,2,3],20

复制返回值：

4

复制

示例2

输入：

[5,2,3],0

复制返回值：

0
  1. #include <stdlib.h>
  2. #include <string.h>
  3. int min(int a, int b) {
  4.     return a < b ? a : b;
  5. }
  6.  
  7. int minMoney(int* arr, int arrLen, int aim ) {
  8.     // write code here
  9.     int dp[aim + 1];
  10.     //dp数组初始化
  11.     for (int i = 0; i < aim + 1; i++) {
  12.         dp[i] = aim + 1;
  13.     }
  14.     dp[0] = 0;
  15.     for (int i = 1; i <= aim; i++) {
  16.         for (int j = 0; j < arrLen; j++) {
  17.             if (arr[j] <= i) {
  18.                 dp[i] = min(dp[i], dp[i - arr[j]] + 1);
  19.             }
  20.         }
  21.     }
  22.     return dp[aim] > aim ? -1 : dp[aim];
  23. }

 8. 最长上升子序列(一)

描述

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 �i 和 �j 满足 �<�i<j 且 ����≥����arri​≥arrj​。

数据范围： 0≤�≤10000≤n≤1000

要求：时间复杂度 �(�2)O(n2)， 空间复杂度 �(�)O(n)

示例1

输入：

[6,3,1,5,2,3,7]

复制返回值：

4

复制说明：

该数组最长上升子序列为 [1,2,3,7] ，长度为4
  1. int max(int a, int b) {
  2.     return a > b ? a : b;
  3. }
  4.  
  5. int LIS(int* arr, int arrLen ) {
  6.     // write code here
  7.     if (arrLen == 0) {
  8.         return 0;
  9.     }
  10.     int dp[arrLen];
  11.     for (int i = 0; i < arrLen; i++) {
  12.         dp[i] = 1;
  13.     }
  14.     for (int i = 0; i < arrLen; i++) {
  15.         for (int j = i - 1; j >= 0; j--) {
  16.             //arr[i] 和 arr[j]相比：
  17.             //小则dp[i] = dp[j] + 1
  18.             //大则不变
  19.             if (arr[i] > arr[j]) {
  20.                 dp[i] = max(dp[i], dp[j] + 1);
  21.             }
  22.         }
  23.     }
  24.     //返回最大值
  25.     int max = dp[0];
  26.     for (int i = 1; i < arrLen; i++) {
  27.         if (max < dp[i]) {
  28.             max = dp[i];
  29.         }
  30.     }
  31.     return max;
  32. }

 9. 最长回文子串

描述

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

数据范围： 1≤�≤10001≤n≤1000

要求：空间复杂度 �(1)O(1)，时间复杂度 �(�2)O(n2)

进阶:  空间复杂度 �(�)O(n)，时间复杂度 �(�)O(n)

示例1

输入：

"ababc"

复制返回值：

3

复制说明：

最长的回文子串为"aba"与"bab"，长度都为3

示例2

输入：

"abbba"

复制返回值：

5
  1. #include <string.h>
  2. int Max(int a, int b) {
  3.     return a > b ? a : b;
  4. }
  5. int getLongestPalindrome(char* A ) {
  6.     // write code here
  7.     int max = 1;
  8.     int len = strlen(A);
  9.     
  10.     for (int i = 0; i < len; i++) {
  11.         for (int j = i + 1; j < len; j++) {
  12.             if (A[i] == A[j]) {
  13.                 int ti = i;
  14.                 int tj = j;
  15.                 int tcnt = 0;
  16.                 while (A[ti] == A[tj] && ti <= tj) {
  17.                     if (ti < tj) {
  18.                         tcnt += 2;
  19.                     }
  20.                     if (ti == tj) {
  21.                         tcnt++;
  22.                     }
  23.                     ti++;
  24.                     tj--;
  25.                 }
  26.                 if (ti >= tj) {
  27.                     max = Max(max, tcnt);
  28.                 } 
  29.             }
  30.         }
  31.     }
  32.     return max;
  33. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/645588
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号