Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
2 made minor edits
source | link
private static int count(String s) {
    int[][] dp = new int [s.length()+1][s.length()+1];
    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                dp[i][j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                dp[i][j] = dp[i+1][j] + dp[i][j-1] +1;
            else
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
        }
    }
    return dp[0][s.length()-1];
}
private static int count2(String s) {
    int[] row1 = new int[s.length()+1];
    int[] row2 = new int[s.length()+1];

    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                row1[j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                row1[j] = row2[j] + row1[j-1] + 1;
            else
                row1[j] = row2[j] + row1[j-1] - row2[j-1];
        }
        // copy row1 into row2
        for(int j=0; j<row1.length; j++)
            row2[j] = row1[j];
    }
    return row1[s.length()-1];
}

So the general pattern to convert recursion to bottom up dp is:

private static int count(String s) {
    int[][] dp = new int [s.length()+1][s.length()+1];
    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                dp[i][j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                dp[i][j] = dp[i+1][j] + dp[i][j-1] +1;
            else
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
        }
    }
    return dp[0][s.length()-1];
}
private static int count2(String s) {
    int[] row1 = new int[s.length()+1];
    int[] row2 = new int[s.length()+1];

    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                row1[j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                row1[j] = row2[j] + row1[j-1] + 1;
            else
                row1[j] = row2[j] + row1[j-1] - row2[j-1];
        }
        // copy row1 into row2
        for(int j=0; j<row1.length; j++)
            row2[j] = row1[j];
    }
    return row1[s.length()-1];
}

So the pattern to convert recursion to dp is:

private int count(String s) {
    int[][] dp = new int [s.length()+1][s.length()+1];
    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                dp[i][j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                dp[i][j] = dp[i+1][j] + dp[i][j-1] +1;
            else
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
        }
    }
    return dp[0][s.length()-1];
}
private int count2(String s) {
    int[] row1 = new int[s.length()+1];
    int[] row2 = new int[s.length()+1];

    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                row1[j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                row1[j] = row2[j] + row1[j-1] + 1;
            else
                row1[j] = row2[j] + row1[j-1] - row2[j-1];
        }
        // copy row1 into row2
        for(int j=0; j<row1.length; j++)
            row2[j] = row1[j];
    }
    return row1[s.length()-1];
}

So the general pattern to convert recursion to bottom up dp is:

1
source | link

The code there is not optimal in terms of space as you can reduce the space complexity to n.

In any case I would recommend thinking as follows when you are trying to convert a brute force recursive solution to dynamic programming.

First look at the recurrence.

f(i,j) = 1                                   if i==j
f(i,j) = f(i+1,j) + f(i,j-1) +1              if str[i] == str[j)
f(i,j) = f(i+1,j) + f(i,j-1) - f(i+1,j-1)    otherwise

Here each i,j pair is a 'state' and each state depends on other states. Dynamic programming stores previously computed states into an array/hashmap/whatever hence allowing us to reuse previously computed states to make the program run faster.

If we are using a 2d array to store the states then state (i,j) is stored in dp[i][j]. State (i-1,j) is stored in dp[i-1][j] and so on.

In any case look at the recurrence relation of the brute force solution. You can see that:

  • For any given state, i depends on the values of i+1 and i
  • For any given state, j depends on the values of j and j-1

Thus we can make the following inference:

  • Since i depends on i, i+1 values, i+1 must be filled before i. Hence i loops from n to 0.
  • Since j depends on j, j-1 values, j-1 must be filled before j. Hence j loops from 0 to n.

So we know the direction of our loops and we can just fill in values accordingly like so:

private static int count(String s) {
    int[][] dp = new int [s.length()+1][s.length()+1];
    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                dp[i][j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                dp[i][j] = dp[i+1][j] + dp[i][j-1] +1;
            else
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
        }
    }
    return dp[0][s.length()-1];
}

And this is basically what is in the link that you posted. f(i, string.length-1)'s state contains the result which is why we return dp[0][s.length()-1].

Time complexity: n^2; Space complexity: n^2

However this is not optimal. Optimal solution below:

Like I mentioned earlier we can make an optimization in terms of space to give us a better solution. This is not done in the link that you posted.

  • Notice that i depends on values of only i and i+1. This means states containing i+2, i+3, ... i+n is useless.

  • Similarly j depends on values of only j and j-1. This means states containing j-2, j-3, ... j-j is useless.

If something like this happens for any parameter of the recurrence, it means that we can reduce the dimension of the array by 1. We can either reduce the dimension i or we can reduce the dimension j (since either i or j can be reduced). Just make sure that the dimension you are reducing is the outer loop.

Here i represents the rows and j represents the columns of the array. Below I will show you how to reduce the i dimension. You can do the same with j but just make sure that if you reduce j, j is in the outer loop.

We are reducing dimension i, we need only 2 rows: row i and row 1+1. We dont need the other rows in the matrix. So let row 1 be row1, let row i+1 be row2.

private static int count2(String s) {
    int[] row1 = new int[s.length()+1];
    int[] row2 = new int[s.length()+1];

    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                row1[j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                row1[j] = row2[j] + row1[j-1] + 1;
            else
                row1[j] = row2[j] + row1[j-1] - row2[j-1];
        }
        // copy row1 into row2
        for(int j=0; j<row1.length; j++)
            row2[j] = row1[j];
    }
    return row1[s.length()-1];
}

The time/space analysis is:

Time complexity: n^2; Space complexity: n

So the pattern to convert recursion to dp is:

  1. Look at the recurrence relation
  2. Figure out the order of the loops
  3. Check to see if any variable x depends on x+-c where c is a constant. If that is the case, we can reduce the space complexity
  4. Compute and store state i,j using previously computed states (unless it is the base case)
  5. Return the result.

Hope this helps.