import Data.Char

checkPluses :: Int -> Int -> Int -> String -> String -> Bool
checkPluses result pVal 0 "" xs = pVal + read1 xs pVal 0 == result
checkPluses result pVal plusCount "" xs =
  checkPluses result pVal plusCount [head xs] (tail xs)
checkPluses result pVal plusCount xs xs'
  | pVal > result = False
  | pVal + r > result = False
  | checkLength xs' plusCount = False
  | (checkPluses result (pVal + r) (plusCount - 1) "" xs') ==
    False = checkPluses result pVal plusCount (xs ++ [head xs']) (tail xs')
  | otherwise = True
  where r = read xs :: Int

checkLength [] r = True
checkLength x 0 = False
checkLength (x:xs) r = checkLength xs (r-1)

read1 [] res acc = acc
read1 (x:xs) res acc
  | acc > res = res + 1
  | otherwise = read1 xs res (acc * 10 + digitToInt x)

int const В_MAX=5000;
int const LEN_A_MAX=1000;
int dp[В_MAX+1][LEN_A_MAX+1];

return dp[B][A.size()-1];

// ...
for (j = i - 1; j >= i - 4 && j >= 0; j--) {
    x = parse_substring(full_string, len - i, len - j);
    for (k = 0; k + x <= n; k++) {
        if (dp[k + x][i] > dp[k][j] + 1)
        {
            dp[k + x][i] = dp[k][j] + 1;
        }
    // ....
    }
}

import Data.Array.Unboxed
import Data.Array.ST
import Control.Monad
import Control.Monad.ST

memoArray :: UArray (Int,Int) Int
memoArray = array ((0,1),(999,5000))
            [((i,j),(-1)) | i <- [0..999], j <- [1..5000]]

main = do
  print (memoArray ! (999,5000))

time ./uArray
-1

real	0m3,399s
user	0m3,268s
sys	0m0,105s

{-# LANGUAGE FlexibleContexts #-}
import Data.Array.Unboxed
import Data.Array.ST
import Control.Monad
import Control.Monad.ST

memoArray :: UArray (Int,Int) Int
memoArray = array ((0,1),(999,5000))
            [((i,j),(-1)) | i <- [0..999], j <- [1..5000]]

main = do
  print (howManyPluses (take 1000 (repeat '1')) 1000)

howManyPluses :: String -> Int -> Int
howManyPluses nums sum
  | sum > 5000 = 1000
  | otherwise = (searchAnswer nums sum) ! (0,sum)

searchAnswer :: String -> Int -> UArray (Int, Int) Int
searchAnswer numbers sum = runSTUArray $ do
  memoArr <- newArray ((0,0), (999,5000)) (-1) :: ST s (STUArray s (Int,Int) Int)
  evaluated <- newArray ((0,0), (999,5000)) False :: ST s (STUArray s (Int,Int) Bool)
  searchInner ((take 1 numbers), (tail numbers)) sum memoArr 0 evaluated

searchInner (nums, nums') sum memoArr len evaluated = do
  isEval <- readArray evaluated (len,sum)
  if isEval == True
    then return memoArr
    else do
    if ((read nums :: Int) > sum) || (((read nums :: Int) /= sum) && (nums' == ""))
      then do
      writeArray memoArr (len,sum) 1000
      writeArray evaluated (len,sum) True
      return memoArr
      else do
      if ((read nums :: Int) == sum) && (nums' == "")
        then do
        writeArray memoArr (len,sum) 0
        writeArray evaluated (len,sum) True
        return memoArr
        else do
        searchInner ((take 1 nums'),(tail nums')) (sum - (read nums :: Int)) memoArr (len + (length nums)) evaluated
        pluses <- readArray memoArr ((len + (length nums)),(sum - (read nums :: Int)))
        searchInner ((nums ++ (take 1 nums')),(tail nums')) sum memoArr len evaluated
        pluses' <- readArray memoArr (len,sum)
        writeArray memoArr (len,sum) (min (pluses + 1) pluses')
        writeArray evaluated (len,sum) True
        return memoArr

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Part {
  int sum;
  vector<int> path;
};

using Table = vector<vector<Part>>;

vector<int> MinAdditions(const string& a, int b) {
  Table table(a.size());
  for (size_t i = 0; i < a.size(); ++i) {
    for (size_t j = i + 1; j != 0; --j) {
      const size_t k = j - 1;
      if (a[k] == '0') {
        continue;
      }
      int c = stoi(a.substr(k, i - k + 1));
      if (c > b) {
        break;
      }
      if (k == 0) {
        table[i].push_back(Part{c, {c}});
      }
      else {
        for (const auto& [s, p] : table[k - 1]) {
          const auto r = c + s;
          if (r <= b) {
            auto newp = p;
            newp.push_back(c);
            table[i].push_back(Part{c + s, move(newp)});
          }
        }
      }
    }
  }
  const auto& lastRow = table[a.size() - 1];
  auto m = min_element(begin(lastRow), end(lastRow),
             [b](const Part& lhs, const Part& rhs) {
               return lhs.sum == b && (rhs.sum != b ||
                      lhs.path.size() < rhs.path.size());
             });
  return m->path;
}

pair<string, int> ReadInput(istream& in) {
  string input;
  getline(in, input);
  const auto i = find(begin(input), end(input), '=');
  string a {begin(input), i};
  int b = stoi(string{i + 1, end(input)});
  return make_pair(move(a), b);
}

ostream& operator<<(ostream& out, const vector<int>& v) {
  char delim[] = {'\0', '+', ' ', '\0'};
  for (int x : v) {
    out << delim << x;
    delim[0] = ' ';
  }
  return out;
}

int main() {
  const auto& [a, b] = ReadInput(cin);
  const auto& p = MinAdditions(a, b);
  cout << p.size() - 1 << endl;
  cerr << p << endl;
}

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Part {
  int sum;
  vector<int> path;
};

using Table = vector<vector<Part>>;

vector<int> MinAdditions(const string& a, int b) {
  Table table(a.size());
  for (size_t i = 0; i < a.size(); ++i) {
    for (size_t j = i + 1; j != 0; --j) {
      const size_t k = j - 1;
      if (a[k] == '0') {
        if (k == i) {
          table[i].insert(table[i].end(), begin(table[i-1]), end(table[i-1]));
        }
        continue;
      }
      int c = stoi(a.substr(k, i - k + 1));
      if (c > b) {
        break;
      }
      if (k == 0) {
        table[i].push_back(Part{c, {c}});
      }
      else {
        for (const auto& [s, p] : table[k - 1]) {
          const auto r = c + s;
          if (r <= b) {
            auto newp = p;
            newp.push_back(c);
            table[i].push_back(Part{c + s, move(newp)});
          }
        }
      }
    }
  }
  const auto& lastRow = table[a.size() - 1];
  auto m = min_element(begin(lastRow), end(lastRow),
             [b](const Part& lhs, const Part& rhs) {
               return lhs.sum == b && (rhs.sum != b ||
                      lhs.path.size() < rhs.path.size());
             });
  return m->path;
}

pair<string, int> ReadInput(istream& in) {
  string input;
  getline(in, input);
  const auto i = find(begin(input), end(input), '=');
  string a {begin(input), i};
  int b = stoi(string{i + 1, end(input)});
  return make_pair(move(a), b);
}

ostream& operator<<(ostream& out, const vector<int>& v) {
  char delim[] = {'\0', '+', ' ', '\0'};
  for (int x : v) {
    out << delim << x;
    delim[0] = ' ';
  }
  return out;
}

int main() {
  const auto& [a, b] = ReadInput(cin);
  const auto& p = MinAdditions(a, b);
  cout << p.size() - 1 << endl;
  cerr << p << endl;
}

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 1000

int array [1000] [5050]; /* 
			    first index -- length
			    second index -- value
			    array contains pluses
			 */
int search (int, int, int) ;
int minimum (int, int) ;

int calculated[1000][5050] ;

char a[1000] ;

int main () {
  char *line = NULL ;
  size_t len = 0 ;
  ssize_t read ;
  read = getline (&line, &len, stdin) ;

  if (-1 == read) { return (0) ;}

  memset (calculated, 0, 1000 * 5050 * sizeof (int)) ;
  memset (array, 0, 1000 * 5050 * sizeof (int)) ;
  void processInput (char *, int) ;
  processInput (line, len) ;
  free (line) ;
  return (0) ;
}

void processInput (char *c, int len) {
  int i ;
  int nulls = 0 ;
  int index = 0 ;
  for (i = 0 ; i < len ; i++) {
    if ('=' == c[i]) { break ; }
    a[index] = c[i] ;
    if ('0' == c[i]) {
      if (nulls < 4) {
	nulls++ ;
      }
    } else {
      nulls = 0 ;
    }
    if (4 != nulls) { index++ ; }
  }

  int length = 4 == nulls ? index + 1 : index ;

  int value = 0 ;
  i++ ;
  for ( ; i < 1010 ; i++) {
    if (c[i] >= '0' && c[i] <= '9') {
      value = value * 10 + c[i] - '0' ;
    } else { break ; }
  }
  
  printf ("%d\n", (search (value, length, 0) - 1)) ;
}

int search (int value, int length, int index) {
  if (index == length) {
    if (0 == value) { return (0) ; }
    else { return (INF) ; }
  }

  if (1 == calculated[index][value]) {
    return (array[index][value]) ;
  }
  
  int pluses_count = (INF) ;
  int current_value = 0 ;
  for (int i = index ; i < length ; i++) {
    current_value = current_value * 10 + a[i] - '0' ;
    if (current_value > value) { break ; }
    pluses_count = minimum (pluses_count,
			    1 + search (value - current_value,
					length, i + 1)) ;
  }

  array[index][value] = pluses_count ;
  calculated[index][value] = 1 ;
  return (pluses_count) ;
}

int minimum (int a, int b) {
  if (a < b) { return (a) ;}
  return (b) ;
}

#include <iostream>
#include <string>

static int
solve(const std::string &a, int offset, int b)
{
    if (offset == a.length()) {
        return (b == 0 ? 0 : -1);
    }

    int x = 0;
    int i;
    for (i = offset; i < a.length() && x <= b; ++i) {
        x = (x*10) + a[i] - '0';
    }

    if (x > b) {
        --i;
        x /= 10;
    }

    if (i == offset) {
        return -1;
    }

    for (int j = i; j > offset; --j) {
        const int r = solve(a, j, b - x);
        if (r >= 0) {
            return (j == a.length() ? 0 : r + 1);
        }
        x /= 10;
    }
    return -1;
}

int
main(void)
{
    std::string line;
    std::cin >> line;

    const int pos = line.find('=');

    const std::string aStr(line.cbegin(), line.cbegin() + pos);
    const std::string bStr(line.cbegin() + pos + 1, line.cend());

    const int b = std::stoi(bStr);

    std::cout << aStr << std::endl;
    std::cout << b << std::endl;
    std::cout << solve(aStr, 0, b) << std::endl;

    return 0;
}

def sub(state, digit, maxpow=4):
    new_state = {}
    for n,(pow,x) in state.items():
        n1  = n - digit
        n10 = n - digit * 10**pow
        if (n1 >= 0):
            new_state[n1] = [1, x+1]
        if (n10 >= 0) and (pow > 0) and (pow <= maxpow):
            new_state[n10] = [pow+1, x]
    return new_state

def find_x(A, B):
    state = {B: [0,-1]}
    for digit in reversed(A):
        state = sub(state, digit)
    x = state.get(0, [None,None])[1]
    return x

test_set = [
    ([9,9,9,8,9,9], 125), 
    ([5,0,2,5], 30), 
    ([1,4,3,1,7,5], 120)
]

for A,B in test_set:
    print(B, A, ': x =', find_x(A, B))

from random import randint
A1000 = [randint(1,9) for _ in range(1000)]
B1000 = sum(A1000)

print(f'{len(A1000)} digits: x =', find_x(A1000, B1000))

$ time python shkola.py
125 [9, 9, 9, 8, 9, 9] : x = 4
30 [5, 0, 2, 5] : x = 1
120 [1, 4, 3, 1, 7, 5] : x = 2
1000 digits: x = 999

python shkola.py  0.21s user 0.00s system 99% cpu 0.215 total