Split the given string into Odds : Digit DP | C ++ program to split the given string into odds ; Function to check whether a string is an odd number or not ; A function to find the minimum number of segments the given string can be divided such that every segment is a odd number ; Declare a splitdp [ ] array and initialize to - 1 ; Build the DP table in a bottom - up manner ; Initially Check if the entire prefix is odd ; If the Given Prefix can be split into Odds then for the remaining string from i to j Check if Odd . If yes calculate the minimum split till j ; To check if the substring from i to j is a odd number or not ; If it is an odd number , then update the dp array ; Return the minimum number of splits for the entire string ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool checkOdd ( string number ) { int n = number . length ( ) ; int num = number [ n - 1 ] - '0' ; return ( num & 1 ) ; } int splitIntoOdds ( string number ) { int numLen = number . length ( ) ; int splitDP [ numLen + 1 ] ; memset ( splitDP , -1 , sizeof ( splitDP ) ) ; for ( int i = 1 ; i <= numLen ; i ++ ) { if ( i <= 9 && checkOdd ( number . substr ( 0 , i ) ) ) splitDP [ i ] = 1 ; if ( splitDP [ i ] != -1 ) { for ( int j = 1 ; j <= 9 && i + j <= numLen ; j ++ ) { if ( checkOdd ( number . substr ( i , j ) ) ) { if ( splitDP [ i + j ] == -1 ) splitDP [ i + j ] = 1 + splitDP [ i ] ; else splitDP [ i + j ] = min ( splitDP [ i + j ] , 1 + splitDP [ i ] ) ; } } } } return splitDP [ numLen ] ; } int main ( ) { cout << splitIntoOdds ( "123456789123456789123" ) << " STRNEWLINE " ; return 0 ; }