编程题中常常遇到动态规划问题，这里做一个记录与分类。

非常见

1. 不冲突字符串的最小删除次数。

   Composition: 给定一个字符串，规定M个不能相邻的字母对，问最少删除多少个字母，可以得到一个合法的字符串。

    5 # 字符串长度
    abcde # 字符串
    3  # 不能相邻的对的个数（M），注意，如果ab是不能相邻的对，那么表示ab, ba都是不合法的。
    ac # pair 1
    ab # pair 2
    de # pair 3
   

   我们将问题转化一下，将其变为“求合法字符串的最大长度l”,然后用总长度L减去l就是删除的字母个数。有了这个转化，我们设置一个状态数组dp[26]， 表示的是以字母dp[i]结尾的合法字符串的最大长度，其中i表示字母a, b, c, d, …, z，共26个取值. 设字符串为str.

   初始条件设置，dp[i] = 0, if str[0] != i, 否则 dp[i] = 1.

   我们从位置1到结束处理str, 对位置k, 该位置的字母为c = str[k], 根据给定的不合法列表，我们可以得出字母c合法的前一个字母集合legal_char_set, 因此 dp[c] = max( dp[l] + 1 ) for every l in legal_char_set . 最后，dp数组中最大值就是合法字符串最大长度l，由此也得到了删除个数。

   当然我们也可以用二阶的DP，即dp[i][j]表示处理到位置i时以字母j结尾的合法字符串的最大长度。更新上，对于当前位置k的字母c, 更新dp[k][c]与上面相同，更新其余dp[k][others]则简单赋值为dp[k-1][others]即可？ 其实二阶真的是完全是没有必要的。

   微软笔试题目，没有做出来… 请教了下师弟，知道了做法。