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.

 

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/

 

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

 

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.

 

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

 

约瑟夫环问题

看解二,妙。
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