Kind of a strange question I know, but here goes:
We are given a string of letters $T$ without any gaps or commas, just letters. Depending on what $T$ is, it could be broken down to form a valid english sentence, or maybe it can't.
For example, if $T=$"HellomynameisOria" then it could be broken down to form "Hello my name is Oria".
If however $T=$"apxlrt" then it can't be broken down to form a meaningful sentence no matter how you slice it.
Let $a_1a_2a_3...a_j$ be a substring of $T$. $C(j)$ is a function that returns $1$ if $a_1a_2...a_j$ can be broken down to a meaningful sentence, and $0$ otherwise.
For example, suppose $T=$"Therearesomegoodthings" then $C(1)=0$, $C(2)=0$, $C(3)=1$,$C(4)=0$,$C(5)=1$ etc...
$C(3)=C(5)=1$ because the words "The" and "There" are valid english words, however $C(2)=0$ because "Th" is not a word.
Given a function $dict(W)$ which returns $1$ if $W$ is a valid english word and $0$ otherwise, find a recursive formula for $C(j)$.
Please note that when I say valid sentence, I mean each word in the sentence is a valid english word (meaning $dict(W)=1$). The sentence itself does not have to make sense. For example "the are you me pizza computer chair" is a valid sentence.
What I did:
I haven't made much meaningful progress. I know that $C(1)=dict(a_1)$ but from there it gets tricky. $C(2)=1$ only if $a_1$ is a word and $a_2$ is a word, or $a_1a_2$ is a word. And when you add $a_3$ it gets even worse.It's a very subtle connection between $C(j)$ and $C(j-1)$.
Edit:
I managed to come to a meaningful observation, but still no mathematical formula.
Consider the string "Thedoorisope". It has $12$ letters and can't be broken down to a sentence. so $C(12)=0$. But if we add the letter "n" then we get "Thedoorisopen" which can be broken down, so $C(13)=1$. This is because "Thedooris" is a valid sentence, so $C(9)=1$, and the word "open" is a word.
In other words, $C(j)=1$ if $C(k)=1$ and $dict(a_{k+1}...a_j)=1$.
As you say, $C(j)=1$ iff there is a $k<j$ such that $C(k)=1$ and $\operatorname{dict}(a_{k+1}\ldots a_j)=1$. This is the case iff there is a $k<j$ such that $C(k)\operatorname{dict}(a_{k+1}\ldots a_j)=1$. That product is always $0$ or $1$, so
$$C(j)=\max_{0\le k<j}\big(C(k)\operatorname{dict}(a_{k+1}\ldots a_j)\big)\;,$$
where we define $C(0)=1$. (That’s to cover the case in which $a_1\ldots a_j$ is a word.)