Technology Sharing

한어Русский язык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  

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
 
// Helper function to extract integer value from substring
int getNumber(char* str, int start, int end) {
    char buffer[12]; // Buffer large enough for max 10 digits + '0'
    int length = end - start + 1;
    strncpy(buffer, str + start, length);
    buffer[length] = '0';
    return atoi(buffer);
}
 
int main() {
    char str[201];
    int M;
    scanf("%s %d", str, &M);
    
    int n = strlen(str);
    int dp[n+1][M+1];
    
    // Initialize dp array with large numbers
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            dp[i][j] = INT_MAX;
        }
    }
    
    // Base case: no splits
    dp[0][0] = 0;
    
    // Dynamic programming to calculate minimum sum
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) { // j can be 0 as well
            if (j == 0) {
                dp[i][j] = getNumber(str, 0, i-1);
            } else {
                for (int k = 1; k < i; k++) { // k starts from 1
                    if (dp[k][j-1] != INT_MAX) {
                        int num = getNumber(str, k, i-1);
                        if (dp[k][j-1] + num < dp[i][j]) {
                            dp[i][j] = dp[k][j-1] + num;
                        }
                    }
                }
            }
        }
    }
    
    // Find the minimum value in dp[n][*] with M splits
    int result = INT_MAX;
    for (int i = 0; i <= M; i++) {
        if (dp[n][i] < result) {
            result = dp[n][i];
        }
    }
    
    printf("%dn", result);
    return 0;
}

Results of the

 Conclusion       

Desire to increase enthusiasm

Perseverance can flatten mountains

！！！