动态规划用法总结（二）

动态规划是一个相对高级的工具，有些本身是动态规划的题可以用动态规划以外，当你无法一眼看穿最优解法时，你可以考虑直接使用动态规划。

动态规划最常见的解法思路步骤是

优点是，基于状态和状态转移，空间复杂度时间复杂度在完全思考前容易预估计，状态一般与输入参数大小直接相关，容易设计，常见的贪心类的，堆栈类的有不少可以用动态规划实现。同时当实现完后，在优化过程中，可能可以推出最优解法。

当然伴随的缺点也是，可能比最优解法在时空复杂度会相对更高

技巧

state[i] = f(state[i-1]);

state[i] = f(state[i-1],...,state[i-k]);

state[i] = a1*state[i-1] + a2*state[i-2] ... + ak*state[i-k]);

stateA[i] = f(stateA[i-1],...,stateA[i-j],stateB[i-1],...,stateB[i-k]);
stateB[i] = g(stateA[i-1],...,stateA[i-m],stateB[i-1],...,stateB[i-n]);

state[i][j] = f(state[i-1][j-1],state[i-1][j],state[i][j-1],...);

state[i*MAXJ+j] = stateold[i][j];

题目6

子数组最大乘积 (贪心)

这道题可以用技巧4, 多个一维状态分别记录, 正数最小绝对值和负数最小绝对值

if(val[i] > 0)
    statepos[i] = min(val[i], statepos[i-1]);
else if(val[i] < 0)
    stateneg[i] = max(val[i], stateneg[i-1]);

alt

题目7

最长回文子串 (遍历)

这道题可以用技巧1, 每次选取中心后, 当前长度是否是回文串与上一次相关

state[len] = state[len-1] && s[center + len + 0..1] == s[center-len]

alt

题目8

兑换零钱(一) (动态规划)

这道题可以用技巧2, 设置状态为金额所需要的个数

state[i] = min(state[i],state[i-coin] + 1);

alt

题目9

最长上升子序列(三) (动态规划)

这道题可以使用技巧2, 建立当前值与在它前面比它小的值的长度关系

state[lower_bound(state.begin(),state.end(),v)] = v;

alt

题目10

最长公共子序列(二) (动态规划)

这道题可以使用技巧5, 记录两个字符串之间匹配的位置的最长长度.

state[i][j] = max(state[i-1][j],state[i][j-1], s1[i] == s2[j] && (state[i-1][j-1]+1))

alt