Skip to content

A Longest Increasing Subsequence (LIS) reduction to solve a problem similar to the Building Bridges Problem. This implementation covers three different approaches: backtracking, greedy and dynamic programming.

License

Notifications You must be signed in to change notification settings

caiozanatelli/LISReduction

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

9 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

LISReduction

This implementation solves a classical problem with a LIS reduction. A street with odd numbers in one side and even numbers in the other is given. On such street there are houses and bars, and the owner of each bar lives in a house located in the opposite sidewalk. As the world cup arrives, the task is to find the maximum number of flags that can be connected from a bar to its owner's home with no crossing flags and only one flag may be connected to each single pair. In order to explore the problem, three solutions were implemented: backtracking, greedy and dynamic programming.

Read the doc and the spec for more information on the project.

About

A Longest Increasing Subsequence (LIS) reduction to solve a problem similar to the Building Bridges Problem. This implementation covers three different approaches: backtracking, greedy and dynamic programming.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published