algorithm CH15 DP

Ex. Rod cutting

input:

• n length of rod
• price of rod with diff. length
  output:
• max price

Assume lenght of rod is n, how many method to cut rod?
Ans.
to prevent exponential complecity, using DP

want to sort q. using DP

need

• optimal substructure
  • 可以獲得子問題的最佳解

簡化rod cutting

• 可以靠最左邊的那一刀
  • for 1<=i<=n

method

• Top-down
  • recursive
  • 導致重複計算
  • T(n) =
• DP bottom-up
  • 把算過的子問題 放在表裡->不用重複計算
  • T(n) =

Subproblem graph

each vertex is a subproblem
exist arc between x and y, means wants to solve x need to solve y first

印出切刀的順序

用一個新的表紀錄對於長度為n的rod
最左邊的刀是哪裡

所以下一刀就是
now_length - s[i] = new_length
s[new_length]

Ex2. LCS

保持相對順序挑出字元，如果兩個sequence抽出的字元一樣

• common subsequence
• 不一定要連續
• LCS
  • 越長越好

暴力法

使用DP需要符合以下兩個特性

• optimal substructure
  • bottom-up
• overlapping subproblem
  • using chart to record ans.

by using optimal structure

• theorem, 可以由最後一個字元來判斷
• 如下圖

定義遞迴關係式

創建c, b table

• c用於找LCS
• b用於紀錄最佳的結果
• pseudo code
  • row major
    

Ex.

• 
  

印出LCS

• 根據b table
  

optimal binary search tree

Actual cost = # of items examined

• For key , cost = depthT() + 1, where depthT() = depth of in BST T.

search cost

• E(x)
  

Ex.

• search cost
  • 越小的cost，樹就越好
    

Observation

• Optimal BST might not have smallest height.
• Optimal BST might not have highest-probability key at root.

force method

• Construct each n-node BST.
• For each, put in keys.
• Then compute expected search cost.
• But there are different BSTs with n nodes.

optimal substructure

divide to 2 subtree

• let r be root of two subtree
  • 人人有機會 個個沒把握
• if j=i-1, tree is empty
  

recursive sol.

pseudo code