Mul DP

[](https://pad.degrowth.net/uploads/0ab40389-e49d-4bb1-83e7-aa98b84e0e51.png)

mul.png

Find the maximum product when placing multiplication operators in a number string.

Problem Analysis:

Given: – A string of N digits (6 ≤ N ≤ 40) – Need to place K multiplication operators (1 ≤ K ≤ 6) – Find the maximum product possible

For example, with string “1231” and K=2: – We need to split it into 3 parts (K+1 parts) – Find the arrangement that gives maximum product

C++ Solution:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

long long getNumber(const string& s, int start, int end) {
    long long num = 0;
    for (int i = start; i <= end; i++) {
        num = num * 10 + (s[i] - '0');
    }
    return num;
}

long long solve(const string& s, int n, int k) {
    // dp[i][j] = maximum product using first i digits with j multiplications
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 2, 0));
    
    // Initialize: no multiplication, just the number itself
    for (int i = 1; i <= n; i++) {
        dp[i][1] = getNumber(s, 0, i - 1);
    }
    
    // Fill the DP table
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= min(i, k + 1); j++) {
            // Try all possible positions for the last multiplication
            for (int m = j - 1; m < i; m++) {
                long long product = dp[m][j-1] * getNumber(s, m, i - 1);
                dp[i][j] = max(dp[i][j], product);
            }
        }
    }
    
    return dp[n][k + 1];
}

int main() {
    int n, k;
    string s;
    
    cin >> n >> k;
    cin >> s;
    
    cout << solve(s, n, k) << endl;
    
    return 0;
}

Python Solution:

def get_number(s, start, end):
    """Extract number from string s from index start to end (inclusive)"""
    return int(s[start:end+1])

def solve(s, n, k):
    """
    Find maximum product by placing k multiplication operators in string s
    dp[i][j] = maximum product using first i digits with j-1 multiplications
    """
    # Initialize DP table
    dp = [[0] * (k + 2) for _ in range(n + 1)]
    
    # Base case: no multiplication, just the number itself
    for i in range(1, n + 1):
        dp[i][1] = get_number(s, 0, i - 1)
    
    # Fill DP table
    for i in range(2, n + 1):
        for j in range(2, min(i, k + 1) + 1):
            # Try all possible positions for the last multiplication
            for m in range(j - 1, i):
                product = dp[m][j-1] * get_number(s, m, i - 1)
                dp[i][j] = max(dp[i][j], product)
    
    return dp[n][k + 1]

def main():
    n, k = map(int, input().split())
    s = input().strip()
    
    print(solve(s, n, k))

if __name__ == "__main__":
    main()

How it works:

  1. Dynamic Programming Approach:

    • dp[i][j] represents the maximum product using the first i digits with j-1 multiplication operators

  2. Base Case:

    • When j=1 (no multiplications), it's just the number formed by the first i digits

  3. Recurrence Relation:

    • For each position i and number of parts j, we try all possible positions m for the last multiplication
    • The product is: dp[m][j-1] * number_from_position_m_to_i

  4. Time Complexity: O(n²×k)

  5. Space Complexity: O(n×k)

For the example input: – Input: n=4, k=2, s=“1231” – The algorithm will find that splitting as 1×2×31 gives maximum product = 62