ডাইনামিকপ্রোগ্রামিংএরসূচনা

ডাইনামিক প্রোগ্রামিং এর সূচনা

আমার আমি :::‌‍ প্রোগ্রামিং ::: পড়াশুনা

দু:খিত - এটা ইংরেজিতে লেখা, আমার সময় নেই এখন অনুবাদ করার! :(

why should you waste your time on DP ?

a. it will help you to understand states of complex graph problems later on

b. its easier to code.

c. it got similarity with combinatorics + counting

d. problemsetters are always finding some new problems that cannot be solved without dynamic programming, so you'll never get short of dp problems

e. its fun!

what is dp ?

dynamic programming is simply dividing a problem into some sub-problems, whose optimal solution will help to find the optimal solution of the main problem. here we save the result of the overlapping sub-problems, so that we wont have to process the same sub-problem for a thousand times.

what is states ?

well, the parameter of the subproblems are called states. this might sound ambiguous right now. thats why we'll solve some problems and read a few tutorial to get that.

stage 0 - reading a tutorial

this is the best tutorial in my opinion for dynamic programming. after reading this, you can proceed.

when you'll get time, and want to clear some things out, you can read about recursion and more basics about dp.

stage 1 - start solving problems

solve these sequentially, take as much time as you need!

a. Problem 15 | Project Eular - can you see the subproblems ?

b. Walking on the Safe Side | UVa 825 - similarity ?

c. Little Red Riding Hood | UVa 11067 - again, did you solve a similar problem before ?

stage 2 - different types of problems

a. Brick Wall Patterns | UVa 900 - again, can you see the subproblems ? does the solution of n depend on some solution for some numbers less than n ?

b. Just the Facts | UVa 568 - :) subproblems again ?

c. Largest Palindrome | UVa 11151 harder! :)

stage 3 - think about a classical problem , can we dp it ?

Longest Increasing Subsequence is the subsequence where a[i] < a[i+1]

like for 1 2 3 2 6 7 the LIS length is 5 - 1 2 3 2 6 7 ,

for 4 2 1 5 9 it is 3 - 4 2 1 5 9 or, 4 2 1 5 9 or, 4 2 1 5 9

if the LIS length is saved in lis[n], while all 1..n-1 are already solved, can we find the solution, using the solutions of before ? just think about it! you dont have to solve it to move to next stage.

stage 4 - reading some problems and think about them, not necessary to solve them

a. ChangingSound | TopCoder - can we do it with backtracking ? if we can, will it work within time limit ? what can we do so that we wont jump on the same subproblems thousand times ?

b. HowManyFiboCalls | TopCoder - can we change the given program a little to save our query ? is it feasible ? what can we do to make it feasible ?