Tag Archives: dynamic programming

make string a postfix notation

Imagine x is an operand and * is a binary operator. We say a string of x and * follows Reverse Polish notation if it is a postfix notation. 

For example strings xx*, x, and xx*xx** follow Reverse Polish notation. 

Given a string of x and *, how many insert, delete, and replace operations are needed to make the string follow the RPN. 

For example, xx* need 0 operation to follow RPN since it already follows RPN. 
x*x needs two operations to become xx* which follows RPN. 
*xx* needs one operation to become xx* which follows RPN. 

Your algorithm should work for a string of size up to 100.

/* Copyleft: Ming Lin <minggr@gmail.com> */
/* http://www.careercup.com/question?id=5762415492857856 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX 300
int cache[MAX][MAX];

int postfix(char *expr, int i, int j)
{
	char c = expr[j];
	int min;
	int tmp;
	int k;

	if (cache[i][j] != -1)
		return cache[i][j];

	if (i == j) {
		if (expr[i] == '*') {
			cache[i][j] = 1;
			return cache[i][j];
		} else {
			cache[i][j] = 0;
			return cache[i][j];
		}
	}

	// why need?
	if (i + 1 == j) {
		if (expr[i] == '*' && expr[j] == '*') {
			cache[i][j] = 2;
			return cache[i][j];
		}
		if (expr[i] == '*' && expr[j] == 'X') {
			cache[i][j] = 1;
			return cache[i][j];
		}
		if (expr[i] == 'X' && expr[j] == '*') {
			cache[i][j] = 1;
			return cache[i][j];
		}
		if (expr[i] == 'X' && expr[j] == 'X') {
			cache[i][j] = 1;
			return cache[i][j];
		}
	}

	min = INT_MAX;
	if (c == '*') {
		for (k = i; k <= j-2; k++) {
			tmp = postfix(expr, i, k) + postfix(expr, k+1, j-1);
			if (tmp < min)
				min = tmp;
		}
	} else {
		//replace 'X' with '*'
		for (k = i; k <= j-2; k++) {
			tmp = postfix(expr, i, k) + postfix(expr, k+1, j-1) + 1;
			if (tmp < min)
				min = tmp;
		}

		//delete 'X'
		tmp = postfix(expr, i, j-1) + 1;
		if (tmp < min)
			min = tmp;

		//add '*'
		for (k = i; k <= j-1; k++) {
			tmp = postfix(expr, i, k) + postfix(expr, k+1, j) + 1;
			if (tmp < min)
				min = tmp;
		}
	}

	cache[i][j] = min;
	return cache[i][j];
}

void init_cache(void)
{
	int i, j;

	for (i = 0; i < MAX; i++)
		for (j = 0; j < MAX; j++)
			cache[i][j] = -1;
}

int main()
{
	char expr[MAX];
	int j;

	init_cache();
	
	while (1) {
		scanf("%s", expr);
		j = strlen(expr) - 1;
		printf("%d\n", postfix(expr, 0, j));
	}
	return 0;
}

 

Flip bits in a range and print number of ‘1’s

http://churmura.com/algorithms/vmware-online-coding-test-for-us-recruitments-hyderabad-event/69549/

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>

int count[100][100];

int flip_bits(int data[], int n)
{
	int len, i, j;
	int max = -1;
	int bits = 0;

	for (i = 0; i < n; i++)
		if (data[i] == 1)
			bits++;

	for (len = 1; len <= n; len++) {
		for (i = 0; i <= n-len; i++) {
			j = i+len-1;
			if (len == 1) {
				if (data[j] == 0)
					count[i][j] = bits + 1;
				else
					count[i][j] = bits - 1;
			} else {
				if (data[j] == 0)
					count[i][j] = count[i][j-1] + 1; 
				else
					count[i][j] = count[i][j-1] - 1; 
			}

			//printf("count[%d][%d]: %d\n", i, j, count[i][j]);
				
			if (max == -1 || count[i][j] > max)
				max =  count[i][j];
		}
	}

	return max;
}

int main()
{
	int data[] = {1, 0, 0, 1, 0, 0, 1, 0};
	int n = 8;

	printf("%d\n", flip_bits(data, n));

	return 0;
}

 

No. 16 – Maximal Length of Incremental Subsequences

Problem: Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

Reference: http://codercareer.blogspot.com/2011/10/no-16-maximum-length-of-incremental.html

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>
#include <stdlib.h>

int maximal(int data[], int n)
{
	int *max;
	int i, j;
	int m, r;
	int cur;

	max = malloc(sizeof(int)*n);

	r = -1;
	max[0] = 1;
	for (i = 1; i < n; i++) {
		m = -1;
		for (j = 0; j < i; j++) {
			if (data[i] > data[j]) {
				cur = max[j] + 1;
			} else
				cur = 1;
			if (m == -1 || cur > m)
				m = cur;
		}
		max[i] = m;

		if (r == -1 || max[i] > r)
			r = max[i];
	}

	free(max);
	return r;
}

int main()
{
	int data[] = {7,2,3,1,5,8,9,6};
	int n = 8;

	printf("%d\n", maximal(data, n));

	return 0;
}

 

No. 25 – Edit Distance

Reference: http://codercareer.blogspot.com/2011/12/no-25-edit-distance.html

Problem: Implement a function which gets the edit distance of two input strings. There are three types of edit operations: insertion, deletion and substitution. Edit distance is the minimal number of edit operations to modify a string from one to the other.

For example, the edit distance between “Saturday” and “Sunday” is 3, since the following three edit operations are required to modify one into the other:

  1. Saturday → Sturday (deletion of ‘a’)
  2. Sturday→ Surday (deletion of ‘t’)
  3. Surday → Sunday (substitution of ‘n’ for ‘r’)

There is no way to achieve it with fewer than three operations.

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int **alloc_two_d(int row, int col)
{
	int **two_d;
	int i, j;

	two_d = malloc(sizeof(int*) * row);
	for (i = 0; i < row; i++)
		two_d[i] = malloc(sizeof(int) * col);

	for (i = 0; i < row; i++)
		for (j = 0; j < col; j++)
			two_d[i][j] = -1;

	return two_d;
}

int edit_distance(char *str1, char *str2)
{
	int **array;
	int len1, len2;
	int i, j;

	len1 = strlen(str1);
	len2 = strlen(str2);
	array = alloc_two_d(len1+1, len2+1);

	for (i = 0; i <= len1; i++) {
		for (j = 0; j <= len2; j++) {
			if (i == 0)
				array[i][j] = j;
			else if (j == 0)
				array[i][j] = i;
			else {
				if (str1[i-1] == str2[j-1])
					array[i][j] = array[i-1][j-1];
				else {
					int min;	

					min = array[i-1][j];
					if (array[i][j-1] < min)
						min = array[i][j-1];
					if (array[i-1][j-1] < min)
						min = array[i-1][j-1];
					
					array[i][j] = min + 1;
				}
			}
		}
	}

	return array[len1][len2];
}

int main()
{
	char *str1 = "Saturday";
	char *str2 = "Sunday";

	printf("%d\n", edit_distance(str1, str2));

	return 0;
}

 

No. 44 – Dynamic Programming on Stolen Values

Problem: There are n houses built in a line, each of which contains some value in it. A thief is going to steal the maximal value in these houses, but he cannot steal in two adjacent houses because the owner of a stolen house will tell his two neighbors on the left and right side. What is the maximal stolen value?

For example, if there are four houses with values {6, 1, 2, 7}, the maximal stolen value is 13 when the first and fourth houses are stolen.

参考:http://codercareer.blogspot.com/2013/02/no-44-maximal-stolen-values.html

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>

int steal(int data[], int n)
{
	int stolen;
	int max;
	int i;

	max = data[0];
	stolen = 1;
	for (i = 1; i < n; i++) {
		if (stolen) {
			if (data[i] > data[i-1])
				max = max - data[i-1] + data[i];
			else
				stolen = 0;
		} else {
			max = max + data[i];
			stolen = 1;
		}
	}

	return max;
}

int main()
{
	int data[] = {6, 1, 2, 7, 3, 9, 4};
	int n = 7;

	printf("max steal: %d\n", steal(data, n));

	return 0;
}

 

约瑟夫环问题

看解二,妙。
http://www.cnblogs.com/EricYang/archive/2009/09/04/1560478.html

妙处在于如何找到子问题,并且找出子问题和原问题的关联。

1, 2, 3, … , k, k+1, k+2, … , n

子问题f(n-1)是:
1, 2, 3, … , k, k+1, … , n-1

但如何得到这个子问题呢?
我的错误想法是将k+1变为k, k+2变为k-1, … , n变为n-1

正确的子问题是这样得到的:
k+1, k+2, … , n, 1, 2, … , k-2, k-1

然后做变换:
x -> x`
k+1 -> 1
k+2 -> 2

n -> k

k-2 -> n-2
k-1 -> n-1

变换公式是:x` = (x-k+n)%n
变回来的公式是:x = (x`+ k)%n

所以有递归式:f(n) = (f(n-1)+k)%n, f(1)=1