Learning Dynamic Programming Has Never Been Easier...

Learning Dynamic Programming Has Never Been Easier...

[GregHogg]

Learn Dynamic Programming and all Data Structures & Algorithms Concepts at AlgoMap.io for free!

[Jupiter___]

Memoisation can be a bit of a trap since it's often faster to do simple calculations than to access memory. Addition is about 10-15x faster than a successful level 1 cache hit iirc, and about 40-50x faster than a level 2 cache hit. This is per memory read, by the way, so nested caching of results usually ends up being slower except for complex matrix multiplications. Even then, you run the risk of evicting your cache-lines and filling them up with the huge matrices you are using, so it ends up harming you down the road.

[nihalbhamrah]

Ngl even tho i can understand complex algorithms and questions in leetcode i never understood fibbonaci series idk why i jever did it properly and gave it time after i got serious maybe thats why

[trooololol]

You don't even need a table for the Fibonacci sequence. You can just use two variables since if you notice, each number is only dependent on the previous two. The 5th number in the sequence has no dependency on the 2nd so there's no point in storing the 2nd

[wka]

Couldn‘t you use the Knapsack problem as an problem that actually needs a table for the dynamic programming algorithm?

[davea]

A tangent: Why would anyone ever perform a calculation of the Fibonacci sequence this way? It isn't like the base case canges, so why would you not jsut start at 0 and loop until you get to the nth Fibonnaci number? What does this get you, other than a programming exercise?

[darknight]

But why is tabulation faster when it calculates every number until n over and over again when the cached one doesnt?
Sure it takes some time to deal with hashes and stuff but only for the first time you enter a given number.
I mean if i run fib(1000) 1, 000, 000 times, i would assume that the cached one is way faster.

[kukosa.places]

Chess
In this matter to you
8
×
8
A standard chess game on an 8×8 square is given. In this process, it is your turn to walk, and in this process you have to defeat the opponent with only one walk.

Example: If you are playing white stones, it is possible to checkmate your opponent in one move by moving the knight on C5 to D7 (Test 1).



Chess pieces are designated as follows: King (horn) - K, Queen (farzin) - Q, Bishop (elephant) - B, Knight (horse) - N, Rook (rux) - R and Pawn (pawn) - P. White and black stones are represented by uppercase and lowercase letters, and empty space by dots, respectively.

Incoming information:
In the first line of the input file
k
(
0
≤
k
≤
1
)
k(0≤k≤1) is an integer i.e. 0 or 1 which means you will continue the game on black or white stones respectively. Get dressed
8
×
8
The game process is depicted on the 8×8 field.

Outgoing data:
You must attack the branch by moving one such stone to another square so that the branch is under attack. Print the initial and final coordinates of the stone to be moved, respectively, separated by spaces (if there are several such solutions, any). A solution is guaranteed.

Examples
1
1
...r....

...pp...




..R....K
C5 D7
2
0
....K.R.
.Pp..P.P
....Bb..
..pP....


....r...

C7 C8
Note:
Pawn movement is only one-sided regardless of whether you play on white or black stones See test 2.


@GregHogg Can you solve this problem