动态规划 题型汇总

简介原问题-->子问题,每个子问题只求解一次。 递归问题中存在重叠子问题 1. 自顶而下:记忆化搜索 2. 自底而上:动态规划 1. 上楼梯问题 1,2,3,4,5,6,7 ..... n 层 每次k层: 记录已经上到前k层时的情况,a[i] = a[i-1] + a[i-2] + ... + a[i - k +1] <一个数组,记录到每个台阶可能走的方法即可>

原问题-->子问题,每个子问题只求解一次。

递归问题中存在重叠子问题

1. 自顶而下:记忆化搜索

2. 自底而上:动态规划


1. 上楼梯问题

1,2,3,4,5,6,7 ..... n 层

每次k层:

记录已经上到前k层时的情况,a[i] = a[i-1] + a[i-2] + ... + a[i - k +1]

<一个数组,记录到每个台阶可能走的方法即可>


2.  路径和最小(从上到下)

14

12 13

9   10  11

5   6    7   8

1   2   3   4   5

实际是无序的一个组合。

用两个a[5], 的数组存储即可,从下到上依次计算路径长度,到最后得到的就是最终结果。


3. 方形表格(r*l),从左上角到右下角最小路径

一个r长度的数组,记录当前列的最小路径,遍历数组(按列),从上到下,判断从上、左那边路径短记录下来。最后求出的值即为最短路径。


4. 分割正整数n(分割出>=2个),使乘积最大。

v[i] 记录长度为i的绳子,切分后成绩的最大值。//最少切分为两端。

对于长度为n的绳子,结果为 max(1*v[n-1], v[2]*v[n-2],  v[3]*v[n-3], ... v[n/2]*v[n-n/2])


5. 小偷偷宝物,不能偷相邻的,最多投多少,每个位置宝物价值不同。

前后关联的线性问题。

从左往右,前一个偷了的价值和,前一个没偷的价值和 ==> 当前偷的价值和(前一个没偷的加当前投了的),当前没偷的价值和(前一个没偷的和前一个偷了的较大的那个值)。


6. 背包问题(容量、价值)

a[n][w]  记录处理前n个商品后,背包容量剩余w 时可以装的最大价值。  第i个商品放/不放。

第i行只依赖于i-1行 ... (通过一个二维数组实现)


7. 最长上升子序列    一整数序列中的最长上升子序列的长度。

从头开始数 记录a[i]结尾的子序列的最大长度。maxLIS 记录以前i元素的最长序列长度。O(n^2)时间复杂度。


O(nlogn) 的时间复杂度。

维护一个栈(按序列长度,单调递增,同时尽可能的存较小的数)最后栈顶元素即为最长子序列的长度。




新加评论 评论标题: