Dynamic Programming

In computer science, mathematics, management science, economics and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.¹

Article Language: English
Exmaple Language: Java
Reading Time: 3min

LeetCode 70. Climbing Stairs

input: number of stairs.
output: return number of distinct ways climb to the top for each time can climb 1 or 2 step(s).

Similar to Fibonacci question. For example, the third step has number of distinct ways climb of the sum of step one and two becuase for each time can climb 1 or 2 step(s). The difference between Fibonacci and climbing stairs is that the first number in Fibonacci is 0 ((0 1 1 2 3 5 8 13 21 …)), while the first number in climbing stairs is 1 becuase it only has one way to climb (1 2 3 5 8 …).
And thus DFS, DP or iteration can be used to resolve this problem, and the time complexities are O(2^n), O(n^2), 和 O(n). Space complexities are O(n) (DFS), O(n) (DP), O(1) (iteration).

class Solution {
    /**
    * @param n: number of stairs
    * @return: distinct ways
    */
    public int climbStairs(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        int prev = 1;
        int cur = 2;
        for (int i = 3; i <= n; i++) {
            int temp = cur;
            cur = prev + cur;
            prev = temp;
        }
        return cur;
    }
}

LeetCode 139. Word Break

input: a String and dictionary of words.
output: whether the string can be fromed by given words in the dictionary.

idx	0	1	2	3	4	5	6	7
L	e	e	t	C	o	d	e
F	F	F	T	F	F	F	T

First of all, get all substring by using DFS, and check whether it exists in the dictionary. But it takes time and space.

Edit Distance

	A	P	P	L	E
idx	0	1	2	3	4
0	1	2	3	4	5
S	1	1	2	3	4
N	2	2	2	3	4
A	3	2	3	3	4
P	4	3	2	3	4

Big Business

input: 2 arrays a and b, where a represents the royalties of the film and b represents the money that the movie can sell. Principal k.
output: return maximum profit can be made by principal (k).

A typical DP, get the maximum profit. Two key points:

It can only making profit if the selling price is higher than the royalities.
Principle can be increased by trading, and thus to be able to get more expensive movies.

Array a and b has a corresponding relationship, so it cannot use sorting. The first thought would be using iteration to find all movies that can make profit. It needs to retain the relationship between profit and royalties becuase it needs to know whether current pinciple can be used to buy a movie.
Using a data structure as Map<a[i], b[i] - a[i>]. Searching while map is not empty and profit is not zero.
The time complexity could be O(n^2) if it’s descending order.
Could use a single loop to find all purchasable movies if sorting royalties. The time complexitiy would be O(nlogn + O(n)), so O(nlogn).

public class BigBusiness {
    /**
     * @param a: The cost of the film
     * @param b: The price of the selling of the film
     * @param k: The principal
     * @return: The answer
     */
    public int bigBusiness(int[] a, int[] b, int k) {
        if (a == null || b == null) {
            return -1;
        }

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < a.length; i++){
                list.add(b[i] - a[i]);
        }
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) > 0 && a[i] <= k) {
                k += list.get(i);
            }
        }
        return k;
    }
}

1.Wiki ↩