//bool dp[i][j] is the state of if the string from i to j is a Palindrome.

//and dp[i][j] only depends on the previous row dp[i][j-1].

//so we can use one-dimension dp array to save some space.

public class Solution {

public int CountSubstrings(string s) {

int count = 0;

bool[] dp = new bool[s.Length + 1];

for(int j = 0; j < s.Length; j++)

{

dp[j+1] = true;

for(int i = 0; i <= j; i++)

{

dp[i] = dp[i + 1] && s[i] == s[j];

```
if(dp[i])
{
count++;
}
}
}
return count;
}
```

}