目录
- 钢条切割
- 如何扩张数据结构
- 区间树
If you can’t win the game, remember what you play game is to make yourself happy. So whatever win or lose you should be happy.
动态规划方法通常用来求解最优化问题，我们通常按如下步骤来设计动态规划的算法：
- 刻画一个最优解的结构特征
- 递归的定义最优解的值
- 计算最优解的值 ，通常采用自底向上的方法
- 利用计算出的信息构造一个最优解
在对动态规划问题进行求解的过程中，分为两种方法
- 自顶向下的方法，即进对整体进行分割，分为整体和剩余。
- 自底向上，求出每一个最优子结构，然后通过自己存储的方式拿到自己想要的子结构。
自上而下的算法缺点在于太多次的递归调用，优点就是不用求出所有的全部情况，自下而上的算法缺点在于需要求出所有的情况，优点在于采用迭代而不是递归调用！
可以使用的递归的方法进行求解:
每次求解的都是最优子问题，然后进行判断，最后得到结果，但是通过递归发现每次都需要从顶到底进行递归，时间复杂度为2的n次方。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
local arr = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 }
local cutRod
cutRod = function(p, n)
if n == 0 then
return 0
end
local q = math.mininteger
for i = 1, n do
q = math.max(q, p[i] + cutRod(p, n - i))
end
return q
end
print(cutRod(arr, 7))
所以对上面的问题进行备忘录的添加，每次求得最小子问题的最优解之后进行存储，然后直接使用即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
local arr = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30, 31, 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 }
local r = {}
r[0] = 0
for i, v in ipairs(arr) do
table.insert(r, math.mininteger)
end
local cutRod
cutRod = function(p, n)
if n == 0 then
return 0
end
local q = math.mininteger
for i = 1, n do
if r[n - i] >= 0 then
q = math.max(q, p[i] + r[n - i])
else
q = math.max(q, p[i] + cutRod(p, n - i))
end
end
r[n] = q
return q
end
接下来考虑另一个算法，矩阵链乘法：
矩阵的相乘，需要计算的次数是前面矩阵的行乘以后面矩阵的列再乘以他们中间相同的数字。
记录一系列矩阵的方法可以使用一个数组，数组中存着他们的行列值。Ai矩阵的行列就是arr[i]和arr[i + 1]
AiAi+1:相乘计算乘法的次数就是i(i+1)(i+2)。接下来使用备忘录以及动态规划的方法来计算至少需要多少次乘法的计算。
通过将a[i,j]分解成子问题，对子问题分别求最优解，然后再相加。a[i,k]和a[k+1,j]然后加上这两个矩阵的乘积arr[i]arr[k]arr[j].
计算的过程为首先计算链长为2的，然后链长为3，一次计算到n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
local arr = { 30, 35, 15, 5, 10, 20, 25 }
local r = {}
local s = {}
local setS = function(i, j, value)
s[i .. ',' .. j] = value
end
local setMemo = function(i, j, value)
r[i .. ',' .. j] = value
end
local getMemo = function(i, j)
if r[i .. ',' .. j] then
return r[i .. ',' .. j]
end
r[i .. ',' .. j] = math.maxinteger
return r[i .. ',' .. j]
end
local matrixMultiplication
matrixMultiplication = function(arr, n)
for i = 1, n do
setMemo(i, i, 0)
end
for l = 2, n do
for i = 1, n - l + 1 do
local j = i + l - 1
setMemo(i, j, math.maxinteger)
for k = i, j - 1 do
local q = getMemo(i, k) + getMemo(k + 1, j) + arr[i] * arr[k + 1] * arr[j + 1]
if q < getMemo(i, j) then
setMemo(i, j, q)
setS(i, j, k)
end
end
end
end
end
matrixMultiplication(arr, 6)
动态规划的原理
- 最优子结构
- 发现重叠子结构，所以建立备忘录
- 重构最优解
最长公共子序列：给定两个序列X，Y，求他们的最长公共子序列。
- 刻画最长公共子序列问题
- 一个递归解
- 计算LCS长度
最优二叉搜索树：建立一个二叉树根据节点被访问的概率，使在这棵树上访问的时候期望值最小。期望的算法为概率乘以深度，除了搜到的概率，还要搜不到的概率。
- 最优二叉搜索树的结构:任意一棵树如果是最优的，那么它的子树也一定是最优的
- 一个递归解:所以i,j的最优解应该为i == j-1的时候就是单个概率，否则就是左子树和右子树的和加上自己的概率。
- 计算最优二叉搜索树的期望搜索的代价。
