动态规划训练第一阶段（for初学者）

A   WordStack
题目链接：http://poj.org/problem?id=2817
一些二进制的基本知识
判断j是否属于集合i：i&(1<<j)
在集合i中去除j：i-(1<<j)或者i&(!(1<<j)) i^(1<<j)
在集合i中加入点j：i|(1<<j);

先预处理出len[i][j]表示第i个字符串与第j个字符串组合能匹配的最大字符数
用一个数的二进制来表示那些字符串，那些字符串还没有选，即二进制位为1的表示已经选了，为0的表示还没有选
Dp[i][j]代表当选取的字符串为i状态，且最后一个选取的字符串是第j个字符串时的最优值
状态转移：枚举某个状态时，枚举一个已选的字符串（即当前状态二进制位为1的位），再枚举一个未选的字符串（当前状态二进制位为0的位），通过这两个字符串的拼接来更新拼接之后新的状态，因为加进了一个没在状态中的字符串，所以状态变成了i|(1<<k) 假设i是当前枚举的状态，k是二进制位为0的位
所以状态转移就为
               dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+len[j][k]);
如果大家仔细观察一下代码中的关键转移部分，会发现：当我们要去更新dp[i|(1<<k)][k]状态时，dp[i][j]肯定已经是求好了的，在这道题目里dp[i][j]就是dp[i|(1<<k)][k]的子结构，每次都尝试着用dp[i|(1<<k)][k]的子结构去更新它
更多状态压缩的题目
http://blog.csdn.net/accry/article/details/6607703

[cpp]
#include<stdio.h>
#include<string.h>
#define max(a,b)(a>b?a:b)
int dp[1<<10+5][11];
int len[11][11];
int n;
char str[11][11];
int main()
{
    int n,i,j,k,x,count;
    int len1,len2,max;
    while(scanf("%d",&n),n)
    {
        memset(len,0,sizeof(len));
        for(i=0;i<n;i++)
            scanf("%s",str[i]);
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                if(i!=j)
                {
                    max=-1;//pay attention
                    len1=strlen(str[i]);
                    len2=strlen(str[j]);
                    for(k=0;k<len1;k++)
                    {
                        count=0;
                        for(x=0;x<len2&&(x+k)<len1;x++)
                        {
                            if(str[i][x+k]==str[j][x]) count++;
                        }
                        if(count>max) max=count;
                    }
                    if(max>len[i][j])
                        len[i][j]=len[j][i]=max;
                }
            }
        }
        memset(dp,0,sizeof(dp));
        for(i=0;i<(1<<n);i++)
            for(j=0;j<n;j++)
            {
                if(i&(1<<j))//if j is in the set of i
                {
                    for(k=0;k<n;k++)
                    {
                        if(!(i&(1<<k)))//if k is not int the set of i,then process dp
                            dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+len[j][k]);
                    }
                }
            }
            max=-1;
            for(i=0;i<(1<<n);i++)
                for(j=0;j<n;j++)
                    if(dp[i][j]>max)
                        max=dp[i][j];
                    printf("%d\n",max);
    }
    return 0;
}

B题
http://poj.org/problem?id=1745
Dp[i][j]代表前i个数能否组成j，那么只要前i-1个数能组成j-a[i]或j+a[i]就可以了，注意j-a[i]<0时要取余，详见代码
dp[i][j]=dp[i-1][j-a[i]] || dp[i-1][j+a[i]];

[cpp]
把取余神马的都提前处理掉，可以加快速度
（bool）dp[i][j]=dp[i-1][j-a[i]]||dp[i-1][j+a[i]]
#include<stdio.h>
#include<string.h>
int a[10001

补充：软件开发 , C++ ,