Technology Sharing

Head Song Resource Library (24) Insert plus sign

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Problem Description

2. Algorithm Idea  

Dynamic programming can be used to solve this problem.

First, split the number string into multiple numbers and use an array nums to store each number. For example, the number string 79846 will be split into the array [7, 9, 8, 4, 6].

Then define a two-dimensional array dp, where dp[i][j] represents the minimum value that can be obtained by inserting j plus signs into the first i numbers. Initialize the dp array to infinity, except for dp[0][0] = 0.

Then use two loops to update the dp array. The outer loop iterates over each digit in the string, and the inner loop iterates over the number of plus signs inserted. For each dp[i][j], you can consider combining the number nums[i] with the previous number to form a new number, or inserting a plus sign between the number nums[i] and the previous number. Take the smaller value of the two cases as the value of dp[i][j].

Finally, the minimum value in the last row of the dp array is the required minimum value.

3. Code Implementation  

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <limits.h>
  4. #include <stdlib.h>
  5. // Helper function to extract integer value from substring
  6. int getNumber(char* str, int start, int end) {
  7. char buffer[12]; // Buffer large enough for max 10 digits + '0'
  8. int length = end - start + 1;
  9. strncpy(buffer, str + start, length);
  10. buffer[length] = '0';
  11. return atoi(buffer);
  12. }
  13. int main() {
  14. char str[201];
  15. int M;
  16. scanf("%s %d", str, &M);
  17. int n = strlen(str);
  18. int dp[n+1][M+1];
  19. // Initialize dp array with large numbers
  20. for (int i = 0; i <= n; i++) {
  21. for (int j = 0; j <= M; j++) {
  22. dp[i][j] = INT_MAX;
  23. }
  24. }
  25. // Base case: no splits
  26. dp[0][0] = 0;
  27. // Dynamic programming to calculate minimum sum
  28. for (int i = 1; i <= n; i++) {
  29. for (int j = 0; j <= M; j++) { // j can be 0 as well
  30. if (j == 0) {
  31. dp[i][j] = getNumber(str, 0, i-1);
  32. } else {
  33. for (int k = 1; k < i; k++) { // k starts from 1
  34. if (dp[k][j-1] != INT_MAX) {
  35. int num = getNumber(str, k, i-1);
  36. if (dp[k][j-1] + num < dp[i][j]) {
  37. dp[i][j] = dp[k][j-1] + num;
  38. }
  39. }
  40. }
  41. }
  42. }
  43. }
  44. // Find the minimum value in dp[n][*] with M splits
  45. int result = INT_MAX;
  46. for (int i = 0; i <= M; i++) {
  47. if (dp[n][i] < result) {
  48. result = dp[n][i];
  49. }
  50. }
  51. printf("%dn", result);
  52. return 0;
  53. }

Results of the

 Conclusion       

Desire to increase enthusiasm

Perseverance can flatten mountains

!!!