动态规划用法总结（一）

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

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

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

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

技巧

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];

题目1

买卖股票的最好时机(一) (贪心)

这道题可以用技巧1, 一维状态来记录从数组起始到上一个的最小值,

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

alt

题目2

求路径 (组合数)

这道题可以用技巧5, 设置多维状态转移

state[i][j] = state[i-1][j] + state[i][j-1]

alt

题目3

通配符匹配 (NFA/DFA)

这道题可以用技巧5, 设置多维状态转移, 相对于上面的求路径，转移方程更复杂

if(p[i] == '*')
    state[i][j] = state[i-1][j] | state[i][j-1] | state[i-1][j-1];
if(p[i] == '?' || p[i] == s[j])
    state[i][j] = state[i-1][j-1];

alt

题目4

最长的括号子串 (栈)

这道题可以使用技巧2,通过分析上一个合法序列和当前构成的关系，转移方程也比题目1更复杂

if(s[i] == '(') continue;
state[i] = s[i-1-state[i-1]] == '(' ? state[i-1] + 2 + state[i-2-state[i-1]]: 0

alt

题目5

连续子数组的最大和 (贪心)

这道题可以使用技巧1, 记录之前的值的前缀和的最小值

state[i] = min(state[i-1], presum[i])

alt