最近开始研究dp写了点题，多少有了点体会。于是有此博客，该系列会继续不定期更新~
一、序列型dp
例：
有一段由A-Z组成的字母信息加密串
加密方式为： A-1，B-2,C-3…Z-26
给定加密后的数字串S[0…N-1]，问有多少种方式解密成字符串
输入 12
输出 2（AB,L）
（1）确定状态
解密数字串即划分成若干段数字，每段数字对应一个字母，
最后一步（最后一段）：对应一个字母，可以是一位数字，也可以是两位（不超过26）
这个数字加密时变成1，2，…? 26
（2）子问题
不妨假设数字串长度为N，需要求前N个字符的解密方式数，我们只需要知道前N-1和N-2个字符的解密方式，然后二者相加即可，那么状态转移方程不难得到
我们设数字串S前i个数字解密成字符串有f[i]种方式 那么显然有
f[i] = f[i-] + f[i-2] (前提是S[i-1]和S[i-2]必须对于一个字母，如果是0显然就不行了)
初始条件f[0] = 1 即解密成空串
边界情况 i = 1 只看最后一个数字
答案为f[N] 时间复杂度和空间复杂度都是O(N)
int solve(string s){
if(s.length() == 0) return 0;
int f[n+1];
f[0] = 0;
for(int i = 1; i <= n; ++i) {
f[i] = 0;
int t = s[i-1] - '0';
if(t >= 1 && t <= 9) f[i] += f[i-1];
if(i >= 2){
t = (s[i-2] - '0')*10 + (s[i-1] - '0');
if(t >= 10 && t <= 26)
f[i] += f[i-2];
}
}
return f[n];
}House Robber
题意：
有一排N栋房子(0~N-1),房子i里有A[i]个金币，有一个小偷想选择一些房子偷金币，但是不能偷任何挨着的两家邻居，否则就会被警察逮住，问最多能偷多少金币
输入：3 8 4
输出： 8(偷第二家)
最后一步：在小偷的最优策略中，有可能偷或者不偷最后一栋房子N-1
情况1：不偷N-1
这种情况最优策略就是前N-1栋房子的最优策略
情况2：偷N-1
仍然需要知道在前N-1栋房子中最多能偷多少，但是能保证不偷第N-2栋房子(因为相邻的不能偷)
那么如何知道在不偷房子N-2的前提下，在前N-1栋房子中最多能偷多少金币呢？
我们设f[i][0]表示不偷房子i-1的前提下，前i栋房子中最多能偷多少金币
f[i][1]表示在偷房子i-1的前提下，前i栋房子中最多能偷多少金币
f[i][0] = max{f[i-1][0],f[i-1][1]}
f[i][1] = f[i-1][0]+A[i-1]
显然这是可以优化的
我们设f[i]表示小偷在前i栋房子中最多偷的金币数 则有
f[i] = max{f[i-1],f[i-2]+A[i-1]}
初始条件f[0] = 0,f[1] = A[0], f[2] = max{A[0],A[1]}
Ans=f[n]
long long solve(int A[], int n) {
if (n == 0) return 0;
long long f[n + 1];
memset(f, 0, sizeof(f));
f[0] = 0;
f[1] = A[0];
//f[2] = max(A[0], A[1]);
for (int i = 2; i <= n; ++i) {
f[i] = max(f[i-1], f[i-2] + A[i-1]);
}
return f[n];
}
House RobberII
题意：
有一圈N栋房子(0~N-1),房子i里有A[i]个金币，有一个小偷想选择一些房子偷金币，但是不能偷任何挨着的两家邻居，否则就会被警察逮住，问最多能偷多少金币
输入：3 8 4
输出： 8(偷第二家)
?
这个题跟上一题的区别是这一题是一圈，也就是说最后一个和第一个是相邻的
我们可以枚举小偷没有偷房子0还是没有偷房子N-1
第一种情况：没有偷房子0 最优策略是小偷对于房子1到N-1的最优策略，于是就化为HouseRobber的做法
第二种情况：没有偷N-1 最优策略就是小偷对于房子0到N-2的最优策略，于是也化为House Robber的做法
二、坐标型dp
最长连续单调子序列
题意：
给定a[0],..,a[n-1]
首先，对于a[i]>a[i+1]>a[i+2]>…a[j]这种情况我们可以将序列翻转，变成求最长连续上升子序列，所以只需要考虑找到最长的a[i]<a[i+1]<a[i+2]<…<a[j]
可以从每个a[i]开始找
最差情况下对于长度为n的序列，需要O(𝑛2)
找到最长的连续子序列i,i+1,i+2,..j,使得a[i]<a[i+1]<a[i+2]<…<a[j],或者a[i]>a[i+1]>a[i+2]>…a[j],输出长度j-i+1
输入：5 1 2 3 4
输出 4(子序列:1,2,3,4)
（1）确定状态
最后一步：对于最优策略，一定有最后一个元素a[j]
第一种情况：最优策略中最长连续上升子序列就是{a[j]},ans = 1
第二种情况：子序列长度大于1，那么最优策略中a[j]前一个元素肯定是a[j-1]（因为是最长连续上升子序列），这种情况一定是a[j-1] < a[j]
因为是最优策略，那么选中的以a[j-1]结尾的连续上升子序列一定是最长的
（2）子问题
转化为求以a[j-1]结尾的最长连续上升子序列
不妨设f[i]表示以a[i]结尾的最长连续上升子序列的长度，通过以上分析不难得到转移方程
f[j] = max{1, f[j-1] + 1 (j > 0 and a[j-1] < a[j])}
情况2必须满足：
j > 0,即j前面只是还有一个元素，a[j] > a[j-1] 满足单调性
初始条件 无
答案为 max{a[1], a[2], … a[n]}
时间复杂度和空间复杂度都为O(n)
int res=0;
void calc(int A[], int n) {
int f[n];
memset(f, 0, sizeof(f));
for(int i = 0; i < n; ++i) {
f[i] = 1;
if(i > 0 && A[i - 1] < A[i])
f[i] = f[i - 1] + 1;
if(f[i] > res)
res = f[i];
}
}
int solve(int A[], int n) {
if(n == 0) return 0;
calc(A, n);
int i, j, t;
i = 0, j = n - 1;
while(i < j) {
t = A[i];
A[i] = A[j];
A[j] = t;
++i;
--j;
}
calc(A, n);
return res;
}
Bomb Enemy
给定一个M*N的网格，每个格子可能是空的，可能有一个敌人，可能有一堵墙，只能在某个空格子里放一个炸弹，炸弹会炸死所有同行同列的敌人，但是不能穿透墙，问最多能炸死几个敌人
输入：E表示敌人，W表示墙，0表示空地
输出 3
先分析一个方向，比如往上
我们假设有敌人或有墙的格子也能放炸弹
--对于有敌人的格子：格子里的敌人被炸死，并继续向上爆炸
--对于有墙的格子，炸弹不能炸死任何人
在(i,j)格放一个炸弹，它能向上炸死的敌人数是:
--(i,j)格是空地：(i-1,j)格能向上炸死的敌人数
--(i,j)格是敌人：(i-1,j)格能向上炸死的敌人数+1
--(i,j)格是墙：0
设UP[i][j]表示在(i,j)格放一个炸弹向上能炸死的敌人数，通过以上分析不难得到状态转移方程
初始条件 Up[0][j] = 0 如果(0,j) 格不是敌人 否则为1
同理可得其它三个方向的状态转移方程
于是Ans[i][j] = Up[i][j] + Down[i][j] + Left[i][j] + Right[i][j]
public class Solution{
public int maxKilledEnemies(char[][] A) {
if (A == null || A.length == 0 || A[0].length()==0) {
return 0;
}
int m = A.length;
int n = A[0].length;
int[][] f = new int[m][n];
int[][] res = new int[m][n];
int i, j;
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
res[i][j]=0;
}
}
//up
for (i = 0; i < m; ++i) {
for (j = 0;j < n; ++j) {
if (A[i][j] == 'W') {
f[i][j] = 0;
}
else {
f[i][j] = 0;
if (A[i][j] == 'E')
f[i][j] = 1;
if (i - 1 >= 0) {
f[i][j] += f[i-1][j];
}
}
res[i][j] += f[i][j];
}
}
//down
for (i = m-1; i >= 0; --i) {
for (j = 0;j < n; ++j) {
if (A[i][j] == 'W') {
f[i][j] = 0;
}
else {
f[i][j] = 0;
if (A[i][j] == 'E')
f[i][j] = 1;
if (i + 1 < m) {
f[i][j] += f[i+1][j];
}
}
res[i][j] += f[i][j];
}
}
//Left
for (i = 0; i < m; ++i) {
for (j = 0;j < n; ++j) {
if (A[i][j] == 'W') {
f[i][j] = 0;
}
else {
f[i][j] = 0;
if (A[i][j] == 'E')
f[i][j] = 1;
if (j - 1 >= 0) {
f[i][j] += f[i][j-1];
}
}
res[i][j] += f[i][j];
}
}
//right
for (i = 0; i < m; ++i) {
for (j = n-1;j >= 0; --j) {
if (A[i][j] == 'W') {
f[i][j] = 0;
}
else {
f[i][j] = 0;
if (A[i][j] == 'E')
f[i][j] = 1;
if (j + 1 < n) {
f[i][j] += f[i-1][j];
}
}
res[i][j] += f[i][j];
}
}
int result = 0;
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
if (A[i][j] == '0') {
if (res[i][j] > result)
result = res[i][j];
}
}
}
return result;
}
}
//当然这个代码可以用方向数组简化
?三、序列+位操作型dp
Counting Bits
题意：
给定N，要求输出0,1,…,N的每个数的二进制表示里1的个数
此题当然可以暴力，但既然是在写dp那就用dp的方法来写
设f[i]表示i的二进制有多少个1，则
f[i] = f[i>>1] + (i mod 2)
初始条件 f[0] = 0
int solve(int x) {
int f[x + 1];
f[0] = 0;
for (int i = 1; i <= x; ++i) f[i] = f[i >> 1] + i % 2;
return f[x];
}