Classic Dynamic Programming VIII

This one was a straightforward DP, usually problems related to Min/Max with a constraint can be solved efficiently with DP. To make this post more interesting and to celebrate Mother's Day, here is a poem for all Mothers using Dynamic Programming (thanks to GAI):

Mom's Dynamic Love

Mom's love, like an algorithm refined,

Dynamic and recursive, forever entwined.

Her hugs are the base case, warm and secure,

While her laughter loops infinitely, that's for sure.

In the matrix of memories, she's the constant term,

Guiding us through life's loops, each twist and turn.

Her kisses, a recursive function, never-ending,

Adding joy to our hearts, forever ascending.

Mom's patience, an optimal solution we seek,

As we debug our lives, sometimes feeling weak.

She patches our errors with love's sweet embrace,

And her smile—oh, that's the perfect base case!

Her advice, a dynamic array of wisdom,

Growing with each iteration, never random.

She sorts out our troubles, like bubbles in a list,

And her warmth? Well, that's the ultimate gist.

So, here's to you, Mom, our dynamic queen,

Your love, an elegant proof we've ever seen.

Happy Mother's Day, with heartfelt recursion,

You're the best function in our life's equation! 🌸❤️

Code is down below, cheers, ACC.

Taking Maximum Energy From the Mystic Dungeon - LeetCode

3147. Taking Maximum Energy From the Mystic Dungeon

Medium

In a mystic dungeon, n magicians are standing in a line. Each magician has an attribute that gives you energy. Some magicians can give you negative energy, which means taking energy from you.

You have been cursed in such a way that after absorbing energy from magician i, you will be instantly transported to magician (i + k). This process will be repeated until you reach the magician where (i + k) does not exist.

In other words, you will choose a starting point and then teleport with k jumps until you reach the end of the magicians' sequence, absorbing all the energy during the journey.

You are given an array energy and an integer k. Return the maximum possible energy you can gain.

 

Example 1:

Input:  energy = [5,2,-10,-5,1], k = 3

Output: 3

Explanation: We can gain a total energy of 3 by starting from magician 1 absorbing 2 + 1 = 3.

Example 2:

Input: energy = [-2,-3,-1], k = 2

Output: -1

Explanation: We can gain a total energy of -1 by starting from magician 2.

 

Constraints:

• 1 <= energy.length <= 105
• -1000 <= energy[i] <= 1000
• 1 <= k <= energy.length - 1

public int MaximumEnergy(int[] energy, int k)
{
    int[] dp = new int[energy.Length];

    int retVal = Int32.MinValue;
    for (int i = 0; i < energy.Length; i++)
    {
        if (i - k < 0) dp[i] = energy[i];
        else dp[i] = Math.Max(energy[i], dp[i - k] + energy[i]);

        if (i + k >= energy.Length) retVal = Math.Max(retVal, dp[i]);
    }
    return retVal;
}