动态规划Dynamic Programing_动态规划dynamic programing表

动态规划的解题步骤

• 第一步：判断是否能够使用动态规划算法
  1.三种适用动规的场景：求可行性，求方案数，求最值。
  2.三种不适用动规的场景：求所有具体方案，输入数据是无序的（背包除外），暴力算法的复杂度已经是多项式级别。
• 判断动态规划的体型
• 使用动规四要素进行解题
  1.状态：坐标，前缀，区间
  2.方程：上一步从哪来，如何依赖更小规模的问题，min/max/sum/or
  初始化：第0行第0列，起点是啥
  答案：终点在哪

动态规划的空间优化技巧——滚动数组Rolling Array

滚动数组Rolling Array

• 如果状态依赖关系只在相邻的几层之间，则可以使用滚动数组进行优化
• 滚动数组可以让空间复杂度降维

题目

109 Triangle 数字三角形

1.特殊情况处理
2.三角形边长为n，存储在n行n列矩阵
3.状态定义：dp[x][y]为从三角形顶点（0，0）到（x，y)的最小路径和
4.初始化：dp[0][0]点得最短路径和为三角形中（0，0）点的5.值自顶向下的方式的多重循环动态规划：
- 初始化本行的最左点和最右点
- 通过上层两点推得当前点得最小路径
6.答案：三角形底层任意一个节点都有可能是最小路径的重点，遍历所有路径终点，返回最小值

非滚动数组转为滚动数组：可以行数取模（%2）来计算，因为行在外层循环，所以滚动行。
1
2
3
4
5
6
7
8
9

朝着哪个方向滚

• 逐行（列）生成数据，就在行（列）上滚动
• 逐行滚动可能从左到右，或者从右至左；逐列滚动可能从上至下，或者从下至上
• 从非滚动变成滚动，只需要：在行（列）上滚动，行（列）index % 滚动行（列）数

630 Knight Shortest Path II

具有有序性，求最优解，由可能使用动态规划
坐标型动态规划
状态转移方程是考虑：从哪儿走到（i，j）这个坐标的
记得重新初始化
1
2
3
4

滚动数组小结

1.滚动数组滚动的是第一重循环的变量，而不是第二重甚至第三重。
2.外层循环决定了是逐行还是逐列。如果外层循环是列，就是逐列；如果外层循环是行，就是逐行。
3.滚动数组也只能滚一个维度，不能两个维度一起滚动。
4.逐行（列）生成数据，就在行（列）上滚动。
5.逐行滚动可能从左至右，或者从右至左；逐列滚动可能从上至下，或者从下至上。
6.从非滚动变成滚动，只需要：在行（列）上滚动，行（列）index % 滚动行（列）数

76 Longest Increasing Subsequence 最长上升子序列（要求时间复杂度为O(n^2)或者O(nlogn)）

subarray 不可以跳；subsequence 可以跳

具有有序性，求最优解，有可能使用动态规划
坐标型动态规划
状态的转移是考虑从哪儿走到（i，j）这个坐标的
1
2
3
4
5

398 Longest Continuous Increasing Subsequence II 最长上升连续子序列 II

具有有序性，求最优解，有可能使用动态规划，不是逐行也不是逐列，是按照值的大小
坐标型动态规划
状态的转移是考虑从哪儿走到（i，j）这个坐标的

1.特殊情况处理
2.设计矩阵的行数和列数
3.把矩阵内的每个点转化成[行，列，值]的形式，存入list
4.按照点的值，从小到大排序
5.定义状态：dp[i][j]表示以坐标(i,j)点结尾的LCIS的长度
6.按照值的大小从小到大排序遍历所有点
7.初始化LCIS为1
8.遍历上下左右四个点（之前的点）
	如果出界，跳过
9.如果周边点小于当前点，那么longest_hash[x,y)]+1为CIS，在所有CIS中选择LCIS
10.最长子序列可能以任一点为终点，在所有Increasing Subsequence中寻找最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

603 Largest Divisible Subset 最大整除子集

利用factor进行优化，不能有1和自身
1