Word-Break Problem (DP)

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.

Suppose dp[i] will be true if string(0....i) can be segmented into space separated dictionary words.

So dp[i] = true in the following two cases->
1.  If( prefix(0...i) will be present in the dictionary.
2. for each j less than i
     dp[j] is true and substr starting from j and of len i-j will be present in dictionary.

Here is the working code for the same.

 bool wordBreakDP(string s)  
 {  
      int n = s.length();  
      int dp[n+1];  
      memset(dp,false,sizeof(dp));  
      dp[0] = true;  
      for(int i=1;i<=n;i++){  
           if(isPresent(s.substr(0,i)))  
                dp[i] = true;  
           else{  
                dp[i]=false;  
                for(int j=i;j>0;j--){  
                     if(dp[j] && isPresent(s.substr(j,i-j))){  
                          dp[i]=true;  
                          break;  
                     }  
                }  
           }  
      }  
      return dp[n];  
 }