最大连续子序列和
int MaxSubseqSum(int a[], int n)
{
　 int max = a[0];
　 int sum = 0;
　 for (int i = 0; i < n; ++i)
　 {
　　 sum += a[i];
　　 if (sum < 0) sum = 0;
　　 if (sum > max)
　　 {
　　　 max = sum;
　　 }
　 }
　 return max;
}

来道题热热身。最大连续子序列和是经典的动态规划例题，几乎所有讲述数据结构的书都会提到。因而不需要过多的解释。不过这里有个变化应用，比较有趣。任选两个数，以下标大的减下标小的，求差能取到的最大值。其实只要把原序列变成差分序列，就转换成了最大连续子序列和问题。

区间动态规划
#define NUM 100
int dp[NUM][NUM];
int sum[NUM][NUM];void DPInit(int a[], int n)
{
　 for (int i = 0; i < NUM; ++i)
　 {
　 　 for (int j = 0; j < NUM; ++j)
　 　 {
　 　 　 dp[i][j] = -1;
　 　 　 sum[i][j] = 0;
　 　 }
　 }
　 for (int i = 0; i < n; ++i) sum[i][i] = a[i];
　 for (int i = 0; i < n; ++i) dp[i][i] = a[i];
　 for (int i = 0; i < n; ++i)
　 {
　 　 for (int j = i; j < n - 1; ++j)
　 　 {
　 　 　 sum[i][j + 1] = sum[i][j] + a[j + 1];
　 　 }
　 }
}
循环实现
void DP(int n)
{
　 for (int k = 1; k < n; ++k)
　 {
　 　 for (int i = 0; i < n; ++i)
　 　 {
　 　 　 for (int j = i; j < i+k; ++j)
　 　 　 {
　 　 　 　 if (dp[i][j] + dp[j + 1][i + k] + sum[i][i + k] > dp[i][i + k])
　 　 　 　 　 dp[i][i + k] = dp[i][j] + dp[j + 1][i + k] + sum[i][i + k];
　 　 　 }
　 　 }
　 }
}
递归实现
int DP(int i, int j)
{
　 if (i == j)
　 {
　 　 return dp[i][j] = sum[i][j];
　 }
　 if (dp[i][j] != -1) return dp[i][j];
　 for (int s = i; s <j; ++s)
　 {
　 　 int l = DP(i, s);
　 　 int r = DP(s + 1, j);
　 　 if (l+ r > dp[i][j])
　 　 {
　 　 　 dp[i][j] = l + r + sum[i][j];
　 　 }
　 }
　 return dp[i][j];
}

区间动态规划。在这里特意分别写了循环和递归的实现，我只是想试试递归是不是也能做。依我现在的理解，所谓的记忆化搜索其实就是动态规划的递归实现版本。

状态压缩动态规划
#define M 5
#define N 10
int dp[N][1<<M];void DPInit()
{
　 for (int i = 0; i < N; ++i)
　 {
　　 for (int j = 0; j < (1<<M); ++j)
　　 {
　　　 dp[i][j] = 0;
　　 }
　 }
}
void dfs(int i, int j, int state, int next)
{
　 if (i + 1 == N) return;
　 if (M == j)
　 {
　　 dp[i + 1][next] += dp[i][state];
　　 return;
　 }
　 if ((state >> j & 1) == 1)
　 {
　　 dfs(i, j + 1, state, next);
　 }
　 if ((state >> j & 1) == 0)
　 {
　　 dfs(i, j + 1, state, next|(1<<j));
　 }
　if (j + 1 < M && ((state >> j & 1) == 0)&& ((state >> (j+1) & 1) == 0))
　 {
　　 dfs(i, j + 2, state, next);
　 }
}
void DP()
{
　 dp[0][0] = 1;
　 for (int i = 0; i < N; ++i)
　 {
　　 for (int j = 0; j < 1 << M; ++j)
　　 {
　　　 if (dp[i][j])
　　　 {
　　　　 dfs(i,0,j,0);
　　　 }
　　 }
　 }
}

状态压缩动态规划。代码基本抄网上的，自己默写了一遍。感觉对状态压缩动态规划的理解还不够深刻，刚尝试着把代码改写，没有成功。问题先放在这里，一定要找时间吃透。

对上述代码的改写。发现自己对记忆化搜索有了点感觉。
int dfs(int i, int j, int state, int next)
{
　 if (0==j&&dp[i][state] != 0) return dp[i][state];
　 if (i + 1 == N)
　 {
　　 return ((1<<M)-1)==state?1:0;
　 }
　 if (M == j)
　 {
　　 return dp[i+1][next]= dfs(i + 1, 0, next, 0);
　 }
　 else
　 {
　　 int cnt1=0, cnt2=0, cnt3=0;
　　 if ((state >> j & 1) == 1)
　　 {
　　　 cnt1=dfs(i, j + 1, state, next);
　　 }
　　 if ((state >> j & 1) == 0)
　　 {
　　　 cnt2=dfs(i, j + 1, state, next | (1 << j));
　　 }
　　 if (j + 1 < M && ((state >> j & 1) == 0) && ((state >> (j + 1) & 1) == 0))
　　 {
　　　 cnt3=dfs(i, j + 2, state, next);
　　 }
　　 if(0==j) dp[i][state] = cnt1 + cnt2 + cnt3;
　　 return cnt1 + cnt2 + cnt3;
　 }
}
void DP()
{
　dfs(0, 0, 0, 0);
}