hdu 4055 dp

这题很不错，参考了别人代码，最后终于理解了。所以做个补充吧。

解题思路：

首先长度为len的字符串对于数列个数是len + 1，我的字符串从0开始，我的数例也是从0这个位置开始。

　1. dp[i][j] 表示第 i 位放数字 j 并满足字符条件的排列数目。（第 i 位，由于从0位置开始算，所以现在长度为 i + 1 ，j 最大为 i+ 1 )

2. 如果str[i - 1]是' I '，(a[i-1] < a[i] ) 那么dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + .. + dp[i-1][1] 也就是第 i - 1 位以小于 j 结尾的情况数之和

如果str[i - 1]是‘D’，(a[i-1] > a[i] ) 那么dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + ... + dp[i-1][i]，这里是难点，因为要令当前位为 j，而前面最大数为 i ,这个时候只需把前面大于等于 j 数+1，就能构造出新的排列了。所以不用关心具体的数值，考虑的是相对的关系。比如 {1, 3, 5, 2, 4}，要在第六位插入3,令 >= 3 的数都+1，于是就构造出新的排列{1, 4, 6, 2, 5, 3}。所以这里我们就直接把结尾是 j 到 i 的数全加上。那些情况都是包含在内的。

3. 利用前缀和sum[i][j]来加速，就不用dp[i][j]了。sum[i][j] 表示第 i 位数字小于等于 j 的总和

代码有两部分，从最初的 dp[ i ][ j ] 状态转移到前缀和数组的改良。方便大家跟上思路。

代码：

#include <bits/stdc++.h>
#define MAXS 1006
#define MOD 1000000007
typedef __int64 ll;
using namespace std;

ll dp[MAXS][MAXS]; // dp[i][j] 表示第i个位置并以j结尾的满足字符条件的排列数。
// 按照状态转移方程一步一步写，会超时，所以我们仔细观察，可以用前缀和。一个sum[i][j]数组来维护。降低复杂度

// 最初版（超时）
int main()
{
  char str[MAXS];
  while(~scanf ("%s",str))
  { //初始化
      int len = strlen(str);
      int stat = 0;
      int end = 0;
    dp[0][1] = 1;//第0个位置，当前长度为1 所以以1结尾
    ll ans = 0;
    for (int i = 1; i <= len ; ++i)
    {    
         for (int j = 1; j <= i+1 ; ++j)
         {
              if (str[i-1] == 'I'){
             stat = 1; end = j-1;
             }
               else if (str[i-1] == 'D')
              {
              stat = j; end = i;
              }
              else {stat = 1; end = i; }    
             dp[i][j] = 0;
           for (int k = stat; k <= end; ++k)
                dp[i][j] = ( dp[i][j] + dp[i-1][k] ) % MOD;

              if (i == len) ans = (ans + dp[i][j]) % MOD;
         }
    }

    printf ("%lld
",ans);
  }
  
 return 0;
}

//改良版

ll sum[MAXS][MAXS];  //前缀和数组 sum[i][j]：表示第i个并且结尾数小于等于j的排列的总数（即 dp[i][1~j] 的和）

int main()
{
  char str[MAXS];
  while(~scanf ("%s",str))
  { 
      int len = strlen(str);
    sum[0][1] = 1;//
    for (int i = 1; i <= len ; ++i)
    {    
        for (int j = 1; j <= i+1 ; ++j)
           {
            //初始化为sum[i][j-1]的值，因为sum[i][j]的值 = sum[i][j-1] + 新增加的相应值
                sum[i][j] = sum[i][j-1];
               if (str[i-1] != 'D')
                 sum[i][j] = (  sum[i][j]  + sum[i-1][j-1] ) % MOD; //是I 和 ？增加的值为 sum[i-1][j-1];
              if (str[i-1] != 'I')//同理 D 和 ？ 增加相应的值
                 sum[i][j] = (  sum[i][j] + sum[i-1][i] - sum[i-1][j-1] + MOD ) % MOD;
          }
    }
     printf ("%lld
",sum[len][len+1]);
  }
  
 return 0;
}