Leetcode动态规划(Python和Java实现)

1. 基本动态规划【上台阶和抢劫问题】

题目要求：

• 给定 n 节台阶，每次可以走一步或走两步，求一共有多少种方式可以走完这些台阶。

解析：因为dp[i] 只与dp[i-1] 和dp[i-2] 有关：

• 因此可以只用两个变量来存储dp[i-1] 和dp[i-2]，
• 使得原来的 O(n)空间复杂度优化为 O(1)复杂度。

def climbstairs(len):
    dp = 0
    dp1 = 1
    dp2 = 2
    if len <= 2:
        return len
    for i in range(2, len):
        dp = dp1 + dp2
        dp1 = dp2
        dp2 = dp

    return dp
1
2
3
4
5
6
7
8
9
10
11
12

题目要求：

• 假如你是一个劫匪，并且决定抢劫一条街上的房子，每个房子内的钱财数量各不相同。
• 如果你抢了两栋相邻的房子，则会触发警报机关。
• 求在不触发机关的情况下最多可以抢劫多少钱。

def rob(arr):
   
    length = len(arr)
    dp = 0
    dp1 = 0
    dp2 = 0
    if length == 0:
        return 0
    if length == 1:
        return arr[0]
    for i in range(0, length):
        dp = max(dp2 + arr[i], dp1)
        dp2 = dp1
        dp1 = dp
    return dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 背包问题【0-1背包和完全背包】

Python 实现0-1背包和完全背包

0-1背包问题:

• dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值
• 我们不将物品 i 放入背包，那么dp[i][j] = dp[i-1][j]
• 如果我们将物品 i 放入背包，假设第 i 件物品体积为 w，价值为 v，那么我们得到 dp[i][j] = dp[i-1][j-w] + v
• 我们只需在遍历过程中对这两种情况取最大值即可
• 假设我们目前考虑物品 i = 2，且其体积为w = 2，价值为v = 3；
• 对于背包容量 j，我们可以得到dp[2][j] = max(dp[1][j], dp[1][j-2] + 3)。
  

def knapsack(weights, values, N, W):
    """
    0-1背包对物品的迭代放在外层，里层的体积或价值逆向遍历
    完全背包对物品的迭代放在里层，外层的体积或价值正向遍历
    :param weights: 物品的重量数组
    :param values: 物品的价值数组
    :param N: 物品的个数
    :param W: 背包的最大承受重量
    :return:
    """
    dp = [0] * (W + 1)  # dp数组用来存储物品的最大价值,dp[i-1] 前 i-1 个物品的最大价值.
    for i in range(1, N + 1):  # 遍历前 i 个物品
        w = weights[i - 1]
        v = values[i - 1]
        for j in range(W, w - 1, -1):  # 这里,dp[j]需要满足的最大重量 j >= W-w, range()为左开右闭区间，所以需要: w-1
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[W]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

完全背包问题

def knapsack2(weights, values, com_N, com_W):  # 完全背包
    """
    用动态规划来解决背包问题:
    完全背包问题的状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v
    :param weights: 物品的重量数组
    :param values: 物品的价值数组
    :param com_N: 物品的个数
    :param com_W: 背包的最大承受重量
    :return:
    """

    dp = [[0] * (com_W + 1)] * (com_N + 1)
    for i in range(1, com_N + 1):  # 遍历前 i 个物品
        w = weights[i - 1]
        v = values[i - 1]
        for j in range(1, com_W + 1):
            if j >= w:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[com_N][com_W]


def knapsack3(weights, values, com_N, com_W):  # 完全背包
    """
    :param weights: 物品的重量数组
    :param values: 物品的价值数组
    :param com_N: 物品的个数
    :param com_W: 背包的最大承受重量
    :return:
    """

    dp = [0] * (com_W + 1)
    for i in range(1, com_N + 1):  # 遍历前 i 个物品
        w = weights[i - 1]
        v = values[i - 1]
        for j in range(w, com_W + 1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[com_W]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

Java 实现0-1背包和完全背包

看下图找出状态转移函数：

//动态规划，0-1背包问题
	public static int knapsack(int[] weight, int[] value, int N, int W){
		int[][] dp = new int[N+1][W+1]; //java 统一赋值为0
		//Arrays.fill(dp, 0);
		System.out.println(dp);
		for (int i = 1; i <=N ; i++) {
			int w = weight[i-1];
			int v = value[i-1];
			for (int j = 1; j <= W; j++) {
				if (j>=w) {
					//0-1完全背包
					//dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w] + v);
					//完全背包公式
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w] + v);
				}
				else {
					dp[i][j] = dp[i-1][j];
				}
				
			}
		}
		
		return dp[N][W];
	}

	public static void main(String[] args) {
		int[] weights = {10, 3, 4, 5, 4};
		int[] values = {24, 2, 9, 10, 9};
		
		System.out.println(Solution.knapsack(weights, values, 5, 13));
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

完全背包和0-1背包输出的都是：28

3. 字符串【字符串匹配和最长子序列】

字符串匹配(非动态规划)，详细解析参考：Implement strStr()

• 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1

Input: haystack = "hello", needle = "ll"
Output: 2
Input: haystack = "aaaaa", needle = "bba"
Output: -1
1
2
3
4

def find_substr(string, substring):
    fri_index = string.find(substring, 0, len(string))
    last_index = string.rfind(substring)  # 0, len(string)默认

    return fri_index, last_index


if __name__ == '__main__':
    s = "this is string example....wow!!!"
    subs = "is"

    fri, last = find_substr(s, subs)
    print("fri = {}  last = {}".format(fri, last))

1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出

fri = 2  last = 5
1

	public int strStr(String haystack, String needle) {
        
		if (needle.isEmpty()) return 0;
        
        int sizeA = haystack.length(), sizeB = needle.length();

		for (int i = 0; i <= sizeA - sizeB; i++) {
			if (haystack.substring(i, i + needle.length()).equals(needle))
				return i;
		}
		return -1;
    }
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		String_Solution solution = new String_Solution();
		
		String string = "aaaaa";
		String string2 = "bba";
		
		int bool = solution.strStr(string, string2);
		
		System.out.println(bool);
		

	}

// indexOf 字符串中查找其子串第一次出现的位置,如果没有找到该子串,则返回-1 
public int strStr2(String haystack, String needle) {
        int index=haystack.indexOf(needle);  
        return  index;
    }
            
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

最长公共子序列：(Longest Common Subsequence)

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.
1
2
3

解析：

1. 最长公共子序列，即两个序列 X 和 Y 的公共子序列中，长度最长的那个，
2. 公共子序列不同于公共字串，公共子序列可以是不连续的，但是前后位置不变。
   

通过上图，我们可看出：两个序列的最长公共子序列的状态转移方程
d p [ i ] [ j ] = { d p [ i − 1 ] [ j − 1 ] + 1 ， i f ： i = j m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) ， i f ： i ≠ j

dp[i][j]={dp[i−1][j−1]+1，if：i=jmax(dp[i−1][j],dp[i][j−1])，if：i=j​​

Python 实现最长序列

def longest_common_subsequence(text1, text2):
    m = len(text1)
    n = len(text2)
    dp = [[0] * (n + 1)] * (m + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]


if __name__ == '__main__':
    text = "acbde"
    text0 = "ace"
    value = longest_common_subsequence(text, text0)
    print(value)

    str1 = "abcbdab"
    str2 = "bdcaba"
    value2 = longest_common_subsequence(str1, str2)
    print(value2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

输出：

3
4
1
2

Java 实现最长序列

public static int lengthOfLIS(String str, String substr) {
		int m = str.length();
		int n = substr.length();
		int dp[][] = new int[m+1][n+1];
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (str.charAt(i-1)==substr.charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1] + 1;
				}
				else {
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		return dp[m][n];
	}
	public static void main(String[] args) {
		String s1 = "abcbdab";
		String s2 = "bdcaba";
		
		System.out.println(Solution.lengthOfLIS(s1, s2));
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

其他子序列问题请点击:

4. 分割类问题【完全平方数相加】

完全平方数相加

• 题目：
  • 给定一个正整数，求其最少可以由几个完全平方数相加构成。
• 解析
  • 对于分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割条件的位置。
  • 我们定义一个一维矩阵dp，其中dp[i] 表示数字i 最少可以由几个完全平方数相加构成。
  • 在本题中，位置i 只依赖 $i-k^2$ 的位置，如 i - 1、i - 4、i - 9 等等，才能满足完全平方分割的条件。
  • 因此dp[i] 可以取的最小值即为1 + min(dp[i-1], dp[i-4], dp[i-9] ...)。

Python代码

def num_squares(key):

    dp = [99] * (key + 1)  # 这里,99代指最大个数。
    dp[0] = 0
    for i in range(1, key + 1):
        for j in range(1, i):
            if j * j <= i:   # 此处，展现的python中for循环的劣势
                dp[i] = min(dp[i], dp[i - j * j] + 1)
            else:
                break
    return dp[key]

print(num_squares(5))
1
2
3
4
5
6
7
8
9
10
11
12
13

java代码

import java.util.Arrays;

public class Solution {
	
	public int numSquares(int n) {
		int dp[] = new int[n+1];
		/* 
		 * 通过Arrays.fill方法就可以为每个元素赋予同样的值
		 * Arrays.fill(arr, 0, 2, 10);  
		 * 0-2,不包括2的索引,打印的是10
		 */
		Arrays.fill(dp, 99);  
		dp[0] = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j*j <= i; j++) {
				dp[i] = Math.min(dp[i], dp[i-j*j] + 1);
			}
		}
		return dp[n];
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 5;
		Solution solution = new Solution();
		
		System.out.println(solution.numSquares(n));
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

输出：

2
1

5. 股票交易

股票交易类问题通常可以用动态规划来解决。对于稍微复杂一些的股票交易类问题，比如需要冷却时间或者交易费用，则可以用通过动态规划实现的状态机来解决。

1. Best Time to Buy and Sell Stock
题目描述

• 给定一段时间内每天的股票价格，已知你只可以买卖各一次，求最大的收益。

题解

• 我们可以遍历一遍数组，在每一个位置 i 时，记录 i 位置之前所有价格中的最低价格，
• 然后将当前的价格作为售出价格，查看当前收益是不是最大收益即可。

def max_profit(prices):
    sell = 0
    buy = -99  # 表示最小值
    for i in range(0, len(prices)):
        buy = max(buy, -prices[i])
        sell = max(sell, buy + prices[i])
    return sell	
1
2
3
4
5
6
7

2. Best Time to Buy and Sell Stock IV
题目描述

• 给定一段时间内每天的股票价格，已知你只可以买卖各 k 次，且每次只能拥有一支股票，求最大的收益。

题解

1. 如果 k 大约总天数，那么我们一旦发现可以赚钱就进行买卖。
2. 如果 k 小于总天数，我们可以建立两个动态规划数组 buy 和sell，对于每天的股票价格，buy[j] 表示在第 j 次买入时的最大收益，sell[j] 表示在第 j 次卖出时的最大收益。

def max_profit_unlimited(prices):
    """
    辅助函数，
    :param prices:每天的股票价格
    :return: maxprofit 最大收益
    """
    maxprofit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            maxprofit += prices[i] - prices[i - 1]
    return maxprofit


def max_profit2(k, prices):

    days = len(prices)

    if days < 2:  # 天数小于2，买入后无法卖出，收益为 0
        return 0

    if k >= days:  # 如果 k 大约总天数，那么我们一旦发现可以赚钱就进行买卖
        return max_profit_unlimited(prices)

    sell = [0] * (k + 1)
    buy = [-99] * (k + 1)  # 表示最小值
    for i in range(0, days):
        for j in range(1, k+1):
            buy[j] = max(buy[j], sell[j-1] - prices[i])
            sell[j] = max(sell[j], buy[j] + prices[i])
    return sell[k]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3. Best Time to Buy and Sell Stock with Cooldown (Medium)

题目描述

• 给定一段时间内每天的股票价格，已知每次卖出之后必须冷却一天，且每次只能拥有一支股票，求最大的收益。

题解

1. 我们可以使用状态机来解决这类复杂的状态转移问题，通过建立多个状态以及它们的转移方式，我们可以很容易地推导出各个状态的转移方程。
   

def max_profit3(prices):
    """
    给定一段时间内每天的股票价格，已知每次卖出之后必须冷却一天，且每次只能拥有一支股票，求最大的收益。
    :param prices:
    :return:
    """
    days = len(prices)
    if days == 0:
        return 0
    buy = [0] * days
    sell = [0] * days
    s1 = [0] * days
    s2 = [0] * days

    s1[0] = buy[0] = -prices[0]

    for i in range(1, days):
        buy[i] = s2[i - 1] - prices[i]
        s1[i] = max(buy[i - 1], s1[i - 1])
        sell[i] = max(buy[i - 1], s1[i - 1]) + prices[i]
        s2[i] = max(s2[i - 1], sell[i - 1])
    return max(sell[days - 1], s2[days - 1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

本笔记参考：LeetCode 101: A LeetCode Grinding Guide (C++ Version)
特此感谢作者高畅Chang Gao的技术支持