动态规划用法总结（三）

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

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

1. 设计状态
2. 设计转移方程
3. 对转移方程时间空间优化
4. 大多数可以改写为递推
5. 边界处理
6. 实现

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

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

技巧

1. 一维状态转移

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

2. 一维状态多值转移

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

3. 一维状态常系数线性转移方程 改写为 矩阵乘法

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

4. 多个一维状态转移

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

5. 多维度状态转移

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

6. 多维度一维转换

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

练手题目

题目11

最长公共子串 (动态规划)

这道题可以用技巧5, 多维状态记录到分别两个字符串的下标对应的最大长度

if(str1[i] == str2[j]){
	state[i+1][j+1] = state[i][j]+1;
}

题目12

编辑距离(二) (动态规划)

这道题可以用技巧5, 多维状态记录到分别两个字符串的下标,能完成编辑后相当对应的最小代价

if(str1[i] == str2[j]){
    state[i+1][j+1] = state[i][j];
}else{
    state[i+1][j+1] = min(
        state[i][j+1] + delete cost,
        state[i][j] + replace cost,
        state[i+1][j] + insert cost
    );
}

题目13

矩阵的最小路径和(动态规划)

这道题可以用技巧5, 设置状态为到每个位置的最小路径和

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

题目14

最大正方形 (动态规划)

这道题可以使用技巧5, 设置状态为到每个位置的最短距离

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

题目15

把数字翻译成字符串 (动态规划)

这道题可以使用技巧2, 记录到每个位置为止的合法方案数

if(is1to9(nums[i])){
    state[i] += state[i-1];
}
if(is10to26(nums[i-1..i])){
    state[i] += state[i-2];
}

题目16

丢棋子问题 (动态规划)

这道题可以使用技巧5, 记录给定棋数和给定次数能探测的最大楼层高度

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

题目17

买卖股票的最好时机(三) (动态规划)

这道题可以使用技巧4和技巧6, 记录到达当前位置时,各个买卖状态的最大收益

if(sale){
	state[enc(i,j)] = max(state[enc(i,j)],state[enc(i,j-1)] + prices[idx]);
}
if(buy){
	state[enc(i,j)] = max(state[enc(i,j)],state[enc(i-1,j)] - prices[idx]);
}

题目18

子数组的最大累加和问题(贪心)

这道题可以使用技巧1, 记录到目前为止最小的前缀和

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

相关文章

动态规划用法总结（一）

动态规划用法总结（二）

动态规划用法总结（三）