Dynamic Programming Part2
Updated:
⚠️ This post was created when I was in high school and is no longer maintained.
1. Fibonacci
Bottomup solution:
algorithm FibonacciDP(n):
{ Not a recursive solution, so don't require an exit !
if n == 1 or n == 2 then
return 1
}
let fib[1 ~ n] be a new array;
fib[1], fib[2] = 1, 1
For i := 3 to n do
fib[i] = fib[i1] + fib[i2]
return fib[n]
Time complexity
O(n)
2. Maxsubarray
2.1 Bruteforce
In this naive solution, we try every possible combination of starting and ending indices, which will result in order of n^2^ time complexity.
algorithm MaxSubarrayNaive(array, len):
max := inf
For left := 0 to len do
sum := 0
For right := left to len do
sum += array[right]
if sum > max then
max = sum
return max
 Time complexity: O(n^2^) (arithmetic progression)
2.2 DP method
Algorithm MaxSubArray(A, n):
Let B be a new array of size n;
B[1] := max(0, A[1])
maxSoFar := 0 > base case
For i:= 2 to n do
B[i] := max(0, B[i1]+A[i])
maxSoFar := max(B[i], maxSoFar)
return maxSoFar
For my understanding, the essence of dynamic programming is to assume that the result of the previous step is always optimal. Consequently, before we start solving problems using DP, we need to find out a base case.
In this problem, it can be that the first element we choose is an optimal one (positive value or 0).
Then, in each step, we have to make 2 decisions. First off, whether or not we should keep the value of the current position:
B[i] := max(0, B[i1]+A[i])
If the summation of the current value A[i]
and the previous optimal result is negative, then the A[i]
definitely has no contribution to the optimal solution, so we drop it by setting B[i]
to 0, which means we cut off the previous subarray from here and start a new subarray accumulation from the next value.
Secondly, we should see if the current optimal choice will contribute to the overall result:
maxSoFar := max(B[i], maxSoFar)
As a final note, I think this algorithm won’t work if all the elements in the input array are negative because the return value will always be 0. To make it work for this circumstance, a few changes are needed.
3. The 01 knapsack problem
Unlike the fractional knapsack problem which can be solved by the greedy strategy, the 01 problem cannot be solved by such an algorithm, although both knapsack problems exhibit the optimalsubstructure property.
3.1 Pseudocode
struct Item {
int weight;
double benifit;
} item;
items := Array[Item](n)
Algorithm 01Knapsack(items, weightLimit):
New dpTable[0 ~ n][0 ~ weightLimit]
n := items.length
For i := 0 to n do
dpTable[i][0] := 0 > initial DP base case
For k := 0 to n do
dpTable[k][0] := 0 > initial base case for each item
For wl := 1 to weightLimit do:
if items[k].weight <= wl then
dpTable[k][wl] := Max(dpTable[k1][wl], dpTable[k][wl  items[k].weight] + items[k].benifit)
else
dpTable[k][wl] := dpTable[k1][wl]
return dpTable[n][weightLimit]
3.2 Intuition

As the code implied above, what we are doing is just building up a DP table in a bottomup manner.

Each cell
dpTable[k][w]
holds the maximum benefit we could possibly get when there are 0 tok
numbers of elements available and the weight limit of the knapsack isw
. 
In the instruction:
Max(dpTable[k1][wl], dpTable[k][wl  items[k].weight] + items[k].benifit)
, we make a decision that whether should we pick the kth item,item[k]
,
For instance,
( here, B[ , ]
<=> dpTable[][]
)
3.3 Time complexity
The time complexity of 01knapsack problem lies in the size of the dpTable
which is n * weightLimit
.
Consequently, if the weightLimit
is something like 2^n^ then T(n) will not be nice…
In a nutshell, this is a pseudopolynomial algorithm
4. Longest Common Subsequence
4.1 Intuition of chopping two strings:
4.2 Intuition of the DP table:
/*
This is what the DP table looks like filled out for the 2 strings
"AGGTAB" and "GXTXAYB".
"" A G G T A B
"" 0 0 0 0 0 0 0
G 0 0 1 1 1 1 1
X 0 0 1 1 1 1 1
T 0 0 1 1 2 2 2
X 0 0 1 1 2 2 2
A 0 1 1 1 2 3 3
Y 0 1 1 1 2 3 3
B 0 1 1 1 2 3 4
Each cell is a subproblem call on the
appropriate substring snippets.
For example, table[G][G] represents
the function call `LCS("AG", "G")`
*/
Leave a comment