Dynamic programming

Posted on Edited on In , Views:

What is Dynamic Programming?

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

[Leetcode 198] House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

1
2
3
4
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

1
2
3
4
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) <=2:
            return max(nums)

        # dp[i] is the maximum amount of money to rob till house[i]
        dp = [None] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])

        return dp[-1]

[Leetcode 746] Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

1
2
3
4
5
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

1
2
3
4
5
6
7
8
9
10
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

Constraints:

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    # dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    # e.g. [10, 15, 20]
    # n = 0, dp[0] = 0 (start)
    # n = 1, dp[1] = 0 (start)
    # n = 2, dp[2] = min(0 + 15, 0 + 10) = 10
    # n = 3, dp[3] = min(10 + 20, 15 + 0) = 15
    # Note: the top is with index 3
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        if n <= 1:
            return 0

        dp = [None] * (n + 1)

        # no cost needed to reach the 0th or 1th staircaes
        dp[0] = 0
        dp[1] = 0

        for i in range(2, n + 1):
            # choose the smaller cost from previous two staircases
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

        return dp[n]

[Leetcode 790] Domino and Tromino Tiling

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 109 + 7.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

Example 1:

1
2
3
Input: n = 3
Output: 5
Explanation: The five different ways are show above.

Example 2:

1
2
Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 1000

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def numTilings(self, n: int) -> int:
        if n <= 1:
            return 1

        m = 1000000007
        dp = [None] * (n + 1) # dp[i] denotes the number of ways to tile an 2*i board
        dp[0], dp[1], dp[2] = 1, 1, 2
        for i in range(3, n + 1):
            dp[i] = (2 * dp[i-1] + dp[i - 3]) % m

        return dp[-1]

[Leetcode 1137] N-th Tribonacci Number

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example 1:

1
2
3
4
5
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

1
2
Input: n = 25
Output: 1389537

Constraints:

  • 0 <= n <= 37
  • The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def tribonacci(self, n: int) -> int:
        a, b, c, = 0, 1, 1
        d = 0

        if n == 0:
            return a
        elif n == 1:
            return b
        elif n == 2:
            return c
        else:
            for _ in range(n - 2):
                d = a + b + c
                a = b
                b = c
                c = d

        return d