Dynamic Programming and Divide and Conquer

Dynamic Programming (often called DP)
Algorithm that solves the problem of the small input size first
And then, solves the problem of the larger size, and finally solves the whole problem by using the solution of the partial problem

• bottom-up approach, find the lowest answer, save it, and solve the upper problem by using the result
• Memoization is the key concept
  • Memoization
    • A technique that utilize the previously calculated values when running a program
    • It speeds up the overall execution by not recalculating
• When dividing datas, partial datas are duplicated and recycled
  • Example: Fibonacci sequence

Divide and Conquer
Algorithm to solve the problems by dividing each other until the problem cannot be divided, and then merging again to get the answer to the problem

• Top-down approach, descending downward to find the upper answer
  • Generally implemented as a recursive function
• When dividing a problem, partial problems do not overlap with each other
  • Example: merge sort, quick sort, etc.

Similarities and differences

• Common points
  • Split the problem into small pieces
• Differences
  • Dynamic programming
    • Partial problems are duplicated and recycled when solving high-level problems
    • Using the Memoization technique (used as an optimization technique to save and recycle answers to partial problems)
  • Divide and Conquer
    • Partial problems do not overlap with each other
    • No Memoization technique

Understanding Dynamic Programming

Fibonacci
Fibonacci sequence : each number is the sum of the two preceding one
0,1,1,2,3,5,8,13,21,34,55,89,144,…

$F_0=0$
$F_1=1$
$F_n=F_{n-1}+F_{n-2}\qquad(n\in{2,3,4,\dots})$

Divide and Conquer

#include<iostream>
#include<cstdio>

using namespace std;

int fibo(int n)
{
	if(n == 0)
		return 0;
	else if(n == 1)
		return 1;

	return fibo(n-1) + fibo(n-2);
}
int main()
{
	int n;
	cin >> n;
	
	cout << fibo(n) << endl;
	
	return 0;
}

Dynamic Programming

#include<iostream>
#include<cstdio>

using namespace std;

int fibo(int n)
{
	int cache[n];
	
	cache[0] = 0;
	cache[1] = 1;
	
	for(int i = 2; i <= n; ++i)
	{
		cache[i] = cache[i-1] + cache[i-2];
	}
	
	return cache[n];
}
int main()
{
	int n;
	cin >> n;
	
	cout << fibo(n) << endl;
	
	return 0;
}

• Dynamic Programming algorithm is faster than Divide and Conqure algorithm

Recursive Call

The same function is called in the function
Functions are managed internally as stack

Practice by C++ code

Palindrome

A palindrome is a word, sentence, verse, or even number that reads the same backward or forward.
Determine that the input number is the same data even if you read the order backwards
ex) level, mom

#include <iostream>
#include <cstdio>
/*
l e v e l
0 1 2 3 4  len 5 size 2

m o m o
0 1 2 3  len 4 size 2 
*/
using namespace std;


bool isPalindrome(char * str_s, int s, int e)
{
	if(s == e) //one charactor
		return true;
		
	if(str_s[s] != str_s[e]) // not palindrome
		return false;
	
	if(e - s > 1) // in case of len is even
		return isPalindrome(str_s, s+1, e-1);
	
	return true;
}

int main()
{
	char str[100];
	scanf("%s", str);
	int len = 0;
	for(int i = 0; str[i] ; ++i)
	{
		++len;
	}
	
	printf("%d\n", len);
	
	if(isPalindrome(str, 0, len-1)) //since array index starts from 0, the -1 is essential
		cout << "the input string is palindrome" << endl;
	else
		cout << "the input string is not palindrome" <<endl;
	
	
	
	return 0;
}

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001

There are 7 ways to express the integer 4 as a combination of 1, 2, and 3 as follows:
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
Given an integer n as input, find the number of ways that “n” can be represented as the sum of 1, 2, 3

f(n): A function that returns the number of cases where an integer n can be created
f(n) = f(n-1) + f(n-2) + f(n-3)

#include<cstdio>
#include<iostream>

using namespace std;

int test(int data)
{
	if(data == 1)
		return 1;
	else if(data == 2)
		return 2;
	else if(data ==3)
		return 4;
	
	return test(data-3) + test(data-2) + test(data-1);
}

int main()
{
	int n;
	cin >> n;
	int count = test(n);
	
	cout << count << endl;
}

Insertion Sort

Insertion sorting is an algorithm that completes a sort by finding and inserting its position by comparing all elements of the data array with the parts of the array that are already sorted, in order from the beginning.

• Insertion sort starts from the second index
• Compare two value : data value (A) and the data of the prior index of the corresponding data (key value)
• If the key value is smaller
  • the A value is copied to the later index
• This is repeated until the key value encounters larger data
  • Insert key value right after location where big data is met

Code Design

index
value

• example of four datas in the list

  1. (5 3 2 4)

  1 0
  3 5
  (3 5 2 4)

  base data index	compared data index
  1	0

  2. (3 5 2 4)

  2 1
  2 5
  (3 2 5 4)
  1 0
  2 3
  (2 3 5 4)

  base data index	compared data index
  2	1

  3. (2 3 5 4)

  3 2
  4 5
  (2 3 4 5)
  2 1
  4 3
  1 0

  base data index	compared data index
  3	2

  4. (2 3 4 5)

Pseudocode

Time Complexity

two for loops : $O(n^2)$

C++ code implementation

#include<iostream>
using namespace std;

void insertionSort(int * data, int size)
{
	for(int i = 0; i < size-1 ; ++i )
	{
		for(int base = i+1 ; base != 0 ; --base)
		{
			if(data[base] < data[base-1])
			{
				int temp = data[base];
				data[base] = data[base-1];
				data[base-1] = temp;
			}
			else
				break;
		}
	}	
}
int main()
{
	int data_i[] = {4,5,3,2,1};

	int len = sizeof(data_i) / sizeof(data_i[0]);
	cout  << len << endl;

	for(int i = 0; i < len; ++i)
		cout << data_i[i] << endl;

	insertionSort(data_i, len);
	
	for(int i = 0; i < len; ++i)
		cout << data_i[i] << endl;
		
	return 0;
	
}