DP

function fib(n)
a = 1, b = 1;
if (n == 1 || n == 2)
return 1;
for i = 3 to n
c = a + b;
a = b;
b = c;
return c;​

iterative

function fib(n)
if (n == 1 || n == 2)
return 1;
else return fib(n-1) + fib(n-2);
What’s the time complexity?
T(n) = T(n-1) + T(n-2) + 1

minimum cost between stations

int cost[N][N] = {

{0, 10, 75, 94},

{-1, 0, 35, 50},

{-1, -1, 0, 80},

{-1, -1, -1, 0} };

minCost(0, N-1) = MIN {
cost[0][N-1],
cost[0][1] + minCost(1, N-1), //어차피 minCost(0,1) = cost[0][1]
minCost(0, 2) + minCost(2, N-1),
... + ...,
minCost(0, N-2) + cost[N-2][N-1] }

minimum cost btw stations 

function minCost(s, d)

if(s == d || s == d - 1)
return cost[s][d];

minValue = cost[s][d];
for i = s+1 to d-1
temp = minCost(s, i) + minCost(i, d);

if(temp < minValue) //cost[s][d]보다 최소값을 가진다면 
minValue = temp;
return minValue;

Recursion + Cache – Overlapping Sub-problems -memoization

memoization

memo[N] = {0};

function fib(n)

if (memo[n] != 0)
return memo[n];

if (n == 1 || n == 2)
memo[n] = 1;

else
memo[n] = fib(n-1) + fib(n-2); //재귀가 들어감

return memo[n]

memo[N][N] = {0};

function minCost(s, d)

if(s == d || s == d - 1) return cost[s][d]; //s가 0칸 1칸 차이는 볼필요도 없음

if(memo[s][d] == 0) //memo[s][d]가 아무것도 갱신안되었으면
minValue = cost[s][d];

for i = s+1 to d-1 //반복문 돌리기
	temp = minCost(s, i) + minCost(i, d); //temp 변수에 넣기 재귀 minCost()존재
		if(temp < minValue)
			minValue = temp;

memo[s][d] = minValue; //내가원하는 memo[s][d] 갱신

return memo[s][d];

Top-Down Dynamic Programming

memoization 

 

Bottom-Up Dynamic Programming

Tabulation

 

 

DP

function fib(n)

int arr[n + 1];
arr[1] = 1;
arr[2] = 1;

for i = 3 to n
	arr[i] = arr[i - 1] + arr[i - 2];

return arr[n];

DP

function minCost(N)

minValue[N];
minValue[0] = 0;
minValue[1] = cost[0][1]; //당근

for i = 2 to N-1
	minValue[i] = cost[0][i]; //minvalue[i] 값을 cost[0][i]로 일단 생각

		for j = 1 to i-1 // i-1까지 비교하기
			if(minValue[i] > minValue[j] + cost[j][i])
				minValue[i] = minValue[j] + cost[j][i];
                
return minValue[N-1]

 

0-1 knapsack problem: take each item or leave it
Fractional knapsack problem: items are divisible

 

p14!!!!!!!!!!!!!!!!!