Can someone give a detailed explanation for this problem!
Define Dp state as dp[i][j]=no of ways of partition of string of length j and last partition has lenght i.
define Dp2 state as dp2[i][j] = no of 1’s in string of length j and last partition has lenght i.
dp2[k][j-i]<=dp2[i][j] where k[1,i] we can find k using binary Search.
state transition :
dp[i][j]=dp[1][j-i] + dp[2][j-i] + dp[3][j-i] + dp[4][j-i] + …+ dp[k][j-i]; here we can use preffix sum to optimise this.