Python Coding Test Course, Exploring Dynamic Programming

1. What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic approach to solving computational problems by breaking down complex problems into simpler subproblems. Generally, it improves performance by remembering the results of subproblems through a recursive approach (memoization technique), preventing repeated calculations.

Dynamic programming is primarily used for solving optimization problems and is effective in finding the optimal solution for a given problem. Many problems can be solved using dynamic programming, with Fibonacci sequences, the longest common subsequence, and the minimum edit distance problem being representative examples.

2. Applied Problem: Maximum Subarray Sum

Problem Description: This problem involves finding the maximum sum of a subarray within a given integer array. A subarray is formed by selecting contiguous elements from the array. For example, in the array [−2,1,−3,4,−1,2,1,−5,4], the maximum sum of a subarray is 6. (This is the sum of [4,−1,2,1].)

2.1 Problem Approach

This problem can be solved using dynamic programming. By iterating through each element of the array, we calculate the maximum sum that includes the current element. We compare the case where the current element is included and where it is not, selecting the larger value. We determine the maximum subarray sum for the current element by utilizing the maximum subarray sum of the previous elements.

3. Problem Solving Process

3.1 Define Variables

First, we will define the following variables:

  • nums: Given integer array
  • max_sum: Maximum subarray sum so far
  • current_sum: Sum of the subarray up to the current position

3.2 Define the Recurrence Relation

The recurrence relation can be defined as follows:

current_sum = max(nums[i], current_sum + nums[i])

Where nums[i] is the current element. We will select the maximum value between the sum that includes the current element and the sum that does not. We then update max_sum each time.

3.3 Initialization and Loop

After initialization, we write a loop to iterate through each element and calculate the maximum sum of the subarray.


def max_sub_array(nums):
    max_sum = nums[0]
    current_sum = nums[0]

    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)

    return max_sum

In the code above, the first element of the array is set as the initial value, and the max_sub_array function is performed repeatedly starting from the second element.

3.4 Code Explanation

Let’s go through the code line by line:

  • max_sum = nums[0]: Initializes the maximum subarray sum to the first element.
  • current_sum = nums[0]: Initializes the current subarray sum to the first element.
  • for i in range(1, len(nums)):: Iterates over the elements starting from the second element of the array.
  • current_sum = max(nums[i], current_sum + nums[i]): Updates the current_sum.
  • max_sum = max(max_sum, current_sum): Updates the max_sum.

3.5 Execution Result

print(max_sub_array([-2,1,-3,4,-1,2,1,-5,4])) # 6

Running the above code will output the maximum subarray sum 6.

4. Techniques of Dynamic Programming

4.1 Memoization and Bottom-Up Approach

Dynamic programming is typically divided into two main techniques:

  • Memoization: A method that saves the results of subproblems to reduce unnecessary calculations. It uses recursive calls, checking for already computed results in each function call.
  • Bottom-Up: A method that systematically solves smaller subproblems before progressing to larger ones. It is generally implemented using loops, which can reduce memory usage.

These techniques can be used to solve a variety of problems.

5. Conclusion

Dynamic programming is a very useful algorithmic technique for solving various optimization problems. Through the maximum subarray sum problem discussed in this lecture, we have learned the fundamental concepts of dynamic programming and methods for problem-solving. This can be applied to various algorithmic problem-solving and is a frequently covered topic in coding tests.

Additionally, I encourage you to practice various problems to deepen your understanding of dynamic programming. This will enhance your algorithmic thinking and help you achieve good results in coding tests.