茉莉Python

voidqueens@hotmail.com

0%

Posted on In

扩展：链表有环，如何判断相交？

分析：如果有环且两个链表相交，则两个链表都有共同一个环，即环上的任意一个节点都存在于两个链表上。因此，就可以判断一链表上俩指针相遇的那个节点，在不在另一条链表上。

无环链表和有环链表是不可能相交的;

两个有环链表若相交，其“整个环上”的所有node一定都重合;

有环链表的相交，情况只有2种：相交于”环上”或相交于”不是环的部分”,即下图所示;

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/link.png

1
https://cloud.tencent.com/developer/article/1045468

Posted on In ,

一.问题:QuerySet object has no attribute _meta

1
2
3
4
5
6
filter() returns a QuerySet also if only one object if found. If you want to return just a model instance, use get()

edit_content = models.Wikistore.objects.filter(id=edit_id)
form = EditorTestForm(instance=edit_content)

# 将filter改为get即可。

二.问题:django.db.utils.InternalError: (1050, “Table ‘wiki’ already exists”)

1
2
3
$ python manage.py migrate wiki --fake 
# wiki是自己的应用名
$ python manage.py migrate

三.问题:执行python manage.py migrate无反应

已有model，修改后重新建模，于是将migrations文件夹中除__init__.py之外其他文件都删掉，再次执行以下步骤python manage.py makemigrations确认成功，执行python manage.py migrate，提示No migrations to apply. 
再次修改，指定表名，再次尝试，问题依旧。

1.排查

python manage.py dbshell 进到数据库里面，查看是否表已存在 
结果：表不存在
检查migrations文件 
结果：文件没问题

2.解决方案

$ python manage.py dbshell # 进入数据库
$ delete from django_migrations where app='your_appname';
$ python manage.py makemigrations(若migrations文件未删除，可不执行这一步)
$ python manage.py migrate # 成功

3.原因分析

(1)查看django_migrations表结构 
建表语句： 
CREATE TABLE "django_migrations" ("id" integer NOT NULL PRIMARY KEY AUTOINCREMENT, "app" varchar(255) NOT NULL, "name" varchar(255) NOT NULL, "applied" datetime NOT NULL); 

(2)原因 
造成多次应用migrations失败的原因是，当前model是修改过的，原来的migrations已经被我删除，但是，重新生成的migrations使用递增整数记名，所以，在django_migrations表中0001，0002等前面几个数字的文件都已被记录，在Django看来，被记录了就相当于已应用，所以，会出现刚开始的No migrations to apply.

4.避免方案

删除migrations文件，请同时到数据库中删除相应记录
可以继续生成新的migrations，旧的就不必理会了

5.其他

执行python manage.py migrate之后，可以使用python manage.py sqlmigrate appname migrations_num(例如python manage.py sqlmigrate user 0002)查看当前migrations文件对应的sql语句。 
另外，在使用上述命令查看0002文件的sql语句时发现，django会新建一个表user_new，然后插入user表中的数据，再把user表删掉，再把user_new重命名为user。所以，修改model的时候，不必担心原有数据会丢失。

四.问题:使用distinct的时候出现了以下问题，DISTINCT ON fields is not supported by this database backend

1
2
3
4
5
6
7
8
9
10
11
12
13
14
文档中的用法：
Author.objects.distinct()
Entry.objects.order_by('pub_date').distinct('pub_date')
Entry.objects.order_by('blog').distinct('blog')
Entry.objects.order_by('author', 'pub_date').distinct('author', 'pub_date')
Entry.objects.order_by('blog__name', 'mod_date').distinct('blog__name', 'mod_date')
Entry.objects.order_by('author', 'pub_date').distinct('author')

但是根据文档中的用法却出了上述问题

后来找到原因，如果是使用mysql的话，distinct()中不能使用任何参数，参数应该在value()中使用
正确使用方法：
obj= Category.objects.values('parentcode','email').distinct()
obj= Category.objects.values('parentcode').distinct()

Posted on Edited on In

一、冒泡排序

一、思想

每次比较两个相邻的元素，如果他们之前的顺序不符就交换位置。
比如5个数从小到大排序，23，64，1，43，21
第一趟：
第一次比较：23，64，1，43，21
第二次比较：23，1，64，43，21
第三次比较：23，1，43，64，21
第四次比较：23，1，43，21，64
经过第一趟的比较后，最大的数字已经到最后面了，接下来只需要比较前四个数字，以此类推。
第二趟：1，23，21，43，64
第三趟：1，21，23，43，64
第四趟：1，21，23，43，64

冒泡排序每一趟只能对一个数进行归位，如果是n个数进行排序，则需要将n-1个数归位，即n-1趟操作
冒泡排序解决了桶排序浪费空间的问题，但是它效率很低。
时间复杂度：O(n^2)

二、用Python实现

`
#!/usr/bin/env python
# coding:utf-8

def bubbleSort(nums):
    for i in range(len(nums) - 1):
        for j in range(len(nums) - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

nums = [5, 6, 3, 1, 6, 2, 5, 33, 3]
print(bubbleSort(nums))
`

二、选择排序

一、思想

第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；
第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；
以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
原始数据：[3,1,0,8,4,2]
第一趟：[0,1,3,8,4,2]
第二趟：[0,1,3,8,4,2]
第三趟：[0,1,2,8,4,3]
第四趟：[0,1,2,3,4,8]
第五趟：[0,1,2,3,4,8]

二、用Python实现选择排序

`
def selectSort(nums):
    for i in range(len(nums)-1):
        print(i)
        min = i
        for j in range(i + 1, len(nums)):
            if nums[min] > nums[j]:
                min = j
        nums[i], nums[min] = nums[min], nums[i]
    return nums`

三、插入排序

一、思想

    插入排序原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。其基本操作就是
将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是稳定的排
序方法，时间复杂度为O(n^2)。

二、步骤

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

二、用Python实现插入排序

`
#!/usr/bin/env python
# coding:utf-8

def insertSort(lists):
    for i in range(1, len(lists)):
        key = lists[i]
        j = i - 1
        while j >= 0:
            if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
    return lists


lists = [4, 6, 2, 4, 7, 3, 9, 2, 1]
print(insertSort(lists))

`

四、快速排序

一、思想

    快速排序是对冒泡排序的一种改进，其基本思想是通过一趟排序将待排序记录分割成独立的两部分，一种一部分记录的关键字均比
另一部分记录的关键字小，最后再分别对这两部分记录继续进行排序，以达到整个序列有序。
    一趟快读排序的具体做法是：附设两个指针low和high，初值分别为low和high，设枢轴记录关键字为pivotkey，则首先从high
所指位置向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录相互交换，然后从low所指位置起向后搜索，找到第一个关键字大
于pivotkey的记录和枢轴记录相互交换，重复这两步直到low=high为止，过程如图。

二、用Python实现快速排序

`
#!/usr/bin/env python
# coding:utf-8

def quickSort(lists, left, right):
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    print("111")
    while left < right:
        while (left < right and lists[right] >= key):
            right -= 1
        lists[left] = lists[right]
        while (left < right and lists[left] <= key):
            left += 1
        lists[right] = lists[left]
    lists[left] = key
    print("key")
    quickSort(lists, low, left - 1)
    quickSort(lists, left + 1, high)
    return lists


lists = [59, 3, 6, 3, 46]
print(quickSort(x, 0, 4))

`

Posted on In

322.零钱兑换

链接：https://leetcode-cn.com/problems/coin-change/

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

题解一|递归|超时：

递归遍历添加所有硬币的情况，每次添加某硬币，则递归遍历总金额-某硬币 的子问题。

    若 当前总金额' 为 0 则表明当前硬币情况有解，返回 0。

    若 当前总金额' 不为 0，则继续添加硬币

        若 当前总金额'-硬币<0 表明不能添加该硬币（无解），尝试添加其他硬币。

        若 当前总金额'-硬币>0 则递归遍历 当前总金额-硬币 的子问题，若子问题无解，尝试添加其他硬币；若子问题有解，则每次添加硬币时记录，硬币数 +1，最终比较取最小值。

    返回情况，若子问题有解，则返回子问题的 最少硬币数，否则返回 -1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        self.res=float('inf')
        def helper(amount,count):
            if amount < 0:
                return
            if amount == 0:
                self.res=min(self.res,count)
            for i in range(len(coins)):
                helper(amount-coins[i],count+1)

        if len(coins)==0:
            return -1
        helper(amount,0)
        if self.res == float('inf'):
            return -1
        return self.res
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount < 0:
            return 0
        res=float('inf')
        for coin in coins:
            if amount-coin < 0:
                continue
            sub=self.coinChange(coins,amount-coin)
            if sub == -1:
                continue
            res=min(res,sub+1)
        return res if res != float('inf') else -1

题解二|记忆化搜索：

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:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def helper(coins,amount,memo):
            if amount == 0:
                return 0
            if amount in memo:
                return memo[amount]

            res=float('inf')

            for coin in coins:
                if amount-coin < 0:
                    continue
                sub=helper(coins,amount-coin,memo)
                if sub == -1:
                    continue
                res=min(res,sub+1)
            if res != float('inf'):
                memo[amount]=res
            else:
                memo[amount]=-1
            return memo[amount]
        memo={}
        return helper(coins,amount,memo)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def helper(amount):
            if amount in memo:
                return memo[amount]
            if amount == 0:
                return 0
            if amount < 0:
                return -1

            res=float('inf')
            for coin in coins:
                sub=helper(amount-coin)
                if sub == -1:
                    continue
                res=min(res,sub+1)
            if res != float('inf'):
                memo[amount]=res
            else:
                memo[amount]=-1
            return memo[amount]
        memo={}
        return helper(coins,amount,memo)

题解三|动态规划：

https://mp.weixin.qq.com/s?__biz=Mzg2NzA4MTkxNQ==&mid=2247486360&idx=2&sn=bebf739b28f51a666af4cb9b30533b55&scene=21#wechat_redirect

1、定义数组含义

dp[i] 保存金额 i 的最小组成数。

2、找出数组递推关系式

遍历 dp 数组，i 遍历区间 [1,amount+1)：

    遍历每种硬币的面值 coin：
        必须满足条件 i>=coin，表示金额必须比硬币面值大。
        dp[i]=min(dp[i],dp(i-coin)+1)，保证保存的是最小的组成数。

若 dp[amount]不为MAX，则返回，否则返回 −1。

3、找到初始值

初试化 dp=[MAX,⋯,MAX]，长度为 amount+1
dp[0]=0，表示 0 元的组成种类为 0

时间复杂度：O(n)
空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp=[float('inf')]*(amount+1)
        dp[0]=0
        for i in range(1,amount+1):
            for coin in coins:
                if i >= coin:
                    dp[i]=min(dp[i],dp[i-coin]+1)
        return dp[-1] if dp[-1] != float('inf') else -1

518. 零钱兑换 II

链接：https://leetcode-cn.com/problems/coin-change-2/

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例 3:

输入: amount = 10, coins = [10] 
输出: 1

注意:

你可以假设：

0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

题解一|回溯|超时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n=len(coins)
        self.res=0
        def helper(first,amount):
            if amount == 0:
                self.res+=1
                return
            
            for i in range(first,len(coins)):
                if coins[i] <= amount:
                    helper(i,amount-coins[i])
        coins.sort()
        helper(0,amount)
        return self.res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n=len(coins)
        self.res=0
        def helper(first,amount):
            if amount == 0:
                self.res+=1
                return 
            for i in range(first,len(coins)):
                if amount >= coins[i]:
                    amount-=coins[i]
                    helper(i,amount)
                    amount+=coins[i]
        coins.sort()
        helper(0,amount)
        return self.res

题解二|动态规划：

参考背包系列
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n=len(coins)
        dp=[[0]*(amount+1) for i in range(n+1)]
        for i in range(n+1):
            dp[i][0]=1
        for i in range(1,n+1):
            for j in range(1,amount+1):
                if j-coins[i-1]>=0:
                    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]]
                else:
                    dp[i][j]=dp[i-1][j]
        return dp[n][amount]

Posted on Edited on In

参考：https://baijiahao.baidu.com/s?id=1641940303518144126&wfr=spider&for=pc

一、红黑树

红黑树除了符合二叉查找树的特性之外，还具有以下特性：

1. 节点是红色或者黑色

2. 根节点是黑色

3. 每个叶子的节点都是黑色的空节点（NULL）

4. 每个红色节点的两个子节点都是黑色的。

5. 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/redblacktree.jpeg

Posted on Edited on In ,

292. Nim 游戏

链接：https://leetcode-cn.com/problems/nim-game/

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4
输出: false 
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
1
2
3
4
5
class Solution:
    def canWinNim(self, n: int) -> bool:
        # 如果上来就踩到 4 的倍数，那就认输吧
        # 否则，可以把对方控制在 4 的倍数，必胜
        return n%4 != 0

319. 灯泡开关

链接：https://leetcode-cn.com/problems/bulb-switcher/

初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。

示例:

输入: 3
输出: 1 
解释: 
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1，因为只有一个灯泡还亮着。

过程:
设总共有 n 个灯泡， 使用i (i∈[1,n])表示第 i 个灯泡。使用 ai(i∈[1,n])表示第i个灯泡的当前状态。

第0轮：全部关闭
第1轮：间隔0个灯泡操作，
操作第1,2,3,……,n个灯泡
第2轮：间隔1个灯泡操作，
操作第2,4,6,……个灯泡
第3轮：间隔2个灯泡操作，
操作第3,6,9,……个灯泡
……
……
第j轮：间隔j-1个灯泡操作，
操作第j,2j,3j,……个灯泡
……
……
第n轮：间隔n-1个灯泡操作，
操作第n个灯泡

1 分析:

1）第j轮的第i个灯泡的状态判断方法：
将包含本轮在内的对第i个灯泡的所有操作次数做和，记为Sij。
若Sij为奇数，说明第i个灯泡，经过j轮以后，是亮着的，因为第0轮一定是关闭的。
同理，若Sij为偶数，说明第i个灯泡，经过j轮以后，是关闭的。

所以问题转变为：
经过n轮，第i个灯泡被操作了奇数次还是偶数次？奇数次则最后是亮的，偶数次则最后是关闭的。

2）观察：
第j轮操作的灯泡的位置，一定是j的倍数。咱们反向观察一下：

第1个灯泡在什么时候会被操作？第1轮
第10个灯泡在什么时候会被操作？第1轮，第2轮，第5轮，第10轮
第20个灯泡在什么时候会被操作？第1轮，第2轮，第4轮，第5轮，第10轮，第20轮

说到这里，会立马发现：第 i 个灯泡只有在第 k 轮会被操作，而 k 一定是 i 的因数。并且 n>=k。所以如果一个数的因数的个数为奇数个，那么它最后一定是亮的，否则是关闭的。
那么问题又转变了：

什么数的因数的个数是奇数个？
答案是完全平方数。

2 为什么完全平方数的因数的个数是奇数个？
设P,A,B 为正整数，如果 P=A*B，则A和B为P的因数。
P的因数A和B总是成对出现。也就是说他们总是一起为 P 的因数个数做贡献。但是如果他们相等呢？这个时候他们一起只会为因数的个数贡献 1。

其次，P=A*A，这种情况对于P来说最多只能出现1次，而这种情况只可能出现在完全平方数中。
所以对于正整数而言，只有完全平方数的因数的个数是奇数个。

综上所述，所以每个完全平方数就是答案

1
2
3
class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(sqrt(n))

Posted on Edited on In

博弈类问题的套路都差不多，其核心思路是在二维 dp 的基础上使用元组分别存储两个人的博弈结果（俩海盗分宝石，俩人拿硬币的问题）。

「石头游戏」：

你和你的朋友面前有一排石头堆，用一个数组 piles 表示，piles[i] 表示第 i 堆石子有多少个。你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后，谁拥有的石头多，谁获胜。

石头的堆数可以是任意正整数，石头的总数也可以是任意正整数，这样就能打破先手必胜的局面了。比如有三堆石头 piles = [1,100,3]，先手不管拿 1 还是 3，能够决定胜负的 100 都会被后手拿走，后手会获胜。

假设两人都很聪明，请你设计一个算法，返回先手和后手的最后得分（石头总数）之差。比如上面那个例子，先手能获得 4 分，后手会获得 100 分，你的算法应该返回 -96。

博弈问题的难点在于，两个人要轮流进行选择，而且都贼精明，应该如何编程表示这个过程呢？

1、定义dp数组的含义

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp16.jpg

dp数组解释：
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp17.jpg

答案是先手和后手最终分数之差，按照这个定义也就是 dp[0][n−1].fir−dp[0][n−1].sec

2、状态转移方程

状态：开始的索引 i，结束的索引 j，当前轮到的人。

1
2
3
4
dp[i][j][fir or sec]
其中：
0 <= i < piles.length
i <= j < piles.length

选择有两个：选择最左边的那堆石头，或者选择最右边的那堆石头

穷举所有状态：
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp18.jpg

状态转移方程：
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp19.jpg

base case:
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp20.jpg

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp21.jpg

推算 dp[i][j] 时需要用到 dp[i+1][j] 和 dp[i][j-1]：所以需要斜着遍历数组

3、实现

1
2
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
    返回先手和后手的得分之差
    
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
n=len(piles)
dp=[[[0]*2 for i in range(n)] for i in range(n)] # 初始化dp

# 初始值
for i in range(n):
    dp[i][i][0]=piles[i]

for i in range(n):
    dp[i][i][0]=piles[i]
    dp[i][i][1]=0

# 斜着遍历数组
for t in range(2,n+1):
    for i in range(n-t+1):
        j=t+i-1

        # 先手选择最左边或者最右边的分数
        left=piles[i]+dp[i+1][j][1]
        right=piles[j]+dp[i][j-1][1]

        # 状态转移
        if left > right:
            dp[i][j][0]=left
            dp[i][j][1]=dp[i+1][j][0]
        else:
            dp[i][j][0]=right
            dp[i][j][1]=dp[i][j-1][0]
res=dp[0][n-1]
return res[0] - res[1]
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
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n=len(piles)
        dp=[[[0]*2 for i in range(n)] for i in range(n)]
        for i in range(n):
            dp[i][i][0]=piles[i]

        for i in range(n):
            dp[i][i][0]=piles[i]
            dp[i][i][1]=0

        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if i==j:
                    continue

                left=piles[i]+dp[i+1][j][1]
                right=piles[j]+dp[i][j-1][1]

                if left >= right:
                    dp[i][j][0]=left
                    dp[i][j][1]=dp[i+1][j][0]
                else:
                    dp[i][j][0]=right
                    dp[i][j][1]=dp[i][j-1][0]
        res=dp[n-1][n-1]
        return res[0] - res[1]

877. 石子游戏

链接：https://leetcode-cn.com/problems/stone-game/

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

示例：

输入：[5,3,4,5]
输出：true
解释：
亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。 

提示：

2 <= piles.length <= 500
piles.length 是偶数。
1 <= piles[i] <= 500
sum(piles) 是奇数。
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
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n=len(piles)
        dp=[[[0]*2 for i in range(n)] for i in range(n)]
        for i in range(n):
            dp[i][i][0]=piles[i]

        for i in range(n):
            dp[i][i][0]=piles[i]
            dp[i][i][1]=0

        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if i==j:
                    continue

                left=piles[i]+dp[i+1][j][1]
                right=piles[j]+dp[i][j-1][1]

                if left >= right:
                    dp[i][j][0]=left
                    dp[i][j][1]=dp[i+1][j][0]
                else:
                    dp[i][j][0]=right
                    dp[i][j][1]=dp[i][j-1][0]
        res=dp[n-1][n-1]
        return res[0] > res[1]

题目有两个条件很重要：一是石头总共有偶数堆，石头的总数是奇数。这两个看似增加游戏公平性的条件，反而使该游戏成为了一个割韭菜游戏。

先手必胜！

1
2
3
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True

Posted on Edited on In

原文：https://mp.weixin.qq.com/s/RXfnhSpVBmVneQjDSUSAVQ

一、背包系列

1、01背包

给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

举个简单的例子，输入如下：

N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]

算法返回 6，选择前两件物品装进背包，总重量 3 小于W，可以获得最大价值 6。

思考：

题目中的物品不可以分割，要么装进包里，要么不装，不能说切成两块装一半。

第一步：

状态：「背包的容量」和「可选择的物品」
选择：「装进背包」或者「不装进背包」
1
2
3
4
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
    for ...
        dp[状态1][状态2][...] = 择优(选择1，选择2...)

第二步：dp数组的定义

明确问题有什么「状态」，现在需要用dp数组把状态表示出来。

「状态」，有两个，也就是说我们需要一个二维dp数组，一维表示可选择的物品，一维表示背包的容量。

dp[i][w]的定义如下：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]。

比如说，如果 dp[3][5] = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。

bad case：
dp[0][..] = dp[..][0] = 0，因为没有物品或者背包没有空间的时候，能装的最大价值就是 0。

答案就是dp[N][W]

1
2
3
4
5
6
7
8
9
10
11
int dp[N+1][W+1]
dp[0][..] = 0
dp[..][0] = 0

for i in [1..N]:
    for w in [1..W]:
        dp[i][w] = max(
            把物品 i 装进背包,
            不把物品 i 装进背包
        )
return dp[N][W]

第三步：根据「选择」，思考状态转移的逻辑

dp[i][w]表示：对于前i个物品，当前背包的容量为w时，这种情况下可以装下的最大价值是dp[i][w]。

如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][w]应该等于dp[i-1][w]。不装的时候，那就继承之前的结果。

如果你把这第i个物品装入了背包，那么dp[i][w]应该等于dp[i-1][w-wt[i-1]] + val[i-1]。

ps：

由于i是从 1 开始的，所以对val和wt的取值是i-1。

dp[i-1][w-wt[i-1]]：你如果想装第i个物品，你怎么计算这时候的最大价值？换句话说，在装第i个物品的前提下，背包能装的最大价值是多少？

寻求剩余重量w-wt[i-1]限制下能装的最大价值，加上第i个物品的价值val[i-1]，这就是装第i个物品的前提下，背包可以装的最大价值。
1
2
3
4
5
6
7
for i in [1..N]:
    for w in [1..W]:
        dp[i][w] = max(
            dp[i-1][w],
            dp[i-1][w - wt[i-1]] + val[i-1]
        )
return dp[N][W]

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
    // vector 全填入 0，base case 已初始化
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i-1] < 0) {
                // 当前背包容量装不下，只能选择不装入背包
                dp[i][w] = dp[i - 1][w];
            } else {
                // 装入或者不装入背包，择优
                dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1], 
                               dp[i - 1][w]);
            }
        }
    }

    return dp[N][W];
}

python:

1
2
3
4
5
6
7
8
9
10
def knapsack(W,N,wt,val):
    dp=[[0]*(W+1) for i in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,W+1):
            if j-wt[i-1] < 0:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j-wt[i-1]]+val[i-1],dp[i-1][j])
    # print(dp)
    return dp[N][W]

2、01背包变体

416. 分割等和子集

链接：https://leetcode-cn.com/problems/partition-equal-subset-sum/

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

思考：

给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

可以先对集合求和，得出sum，把问题转化为背包问题：给一个可装载重量为sum/2的背包和N个物品，每个物品的重量为nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？

第一步：

状态：「背包的容量」和「可选择的物品」
选择：「装进背包」或者「不装进背包」

第二步：dp数组的定义

dp[i][j] = x表示，对于前i个物品，当前背包的容量为j时，若x为true，则说明可以恰好将背包装满，若x为false，则说明不能恰好将背包装满。

比如说，如果dp[4][9] = true，其含义为：对于容量为 9 的背包，若只是用前 4 个物品，可以有一种方法把背包恰好装满。

或者说对于本题，含义是对于给定的集合中，若只对前 4 个数字进行选择，存在一个子集的和可以恰好凑出 9。

根据这个定义，我们想求的最终答案就是dp[N][sum/2]，base case 就是dp[..][0] = true和dp[0][..] = false，因为背包没有空间的时候，就相当于装满了，而当没有物品可选择的时候，肯定没办法装满背包。

第三步：根据「选择」，思考状态转移的逻辑

根据「选择」对dp[i][j]得到以下状态转移：

如果不把nums[i]算入子集，或者说你不把这第i个物品装入背包，那么是否能够恰好装满背包，取决于上一个状态dp[i-1][j]，继承之前的结果。

如果把nums[i]算入子集，或者说你把这第i个物品装入了背包，那么是否能够恰好装满背包，取决于状态dp[i - 1][j-nums[i-1]]。

首先，由于i是从 1 开始的，而数组索引是从 0 开始的，所以第i个物品的重量应该是nums[i-1]，这一点不要搞混。

dp[i - 1][j-nums[i-1]]也很好理解：你如果装了第i个物品，就要看背包的剩余重量j - nums[i-1]限制下是否能够被恰好装满。

换句话说，如果j - nums[i-1]的重量可以被恰好装满，那么只要把第i个物品装进去，也可恰好装满j的重量；否则的话，重量j肯定是装不满的。

c++:

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
bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    // 和为奇数时，不可能划分成两个和相等的集合
    if (sum % 2 != 0) return false;
    int n = nums.size();
    sum = sum / 2;
    vector<vector<bool>> 
        dp(n + 1, vector<bool>(sum + 1, false));
    // base case
    for (int i = 0; i <= n; i++)
        dp[i][0] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (j - nums[i - 1] < 0) {
               // 背包容量不足，不能装入第 i 个物品
                dp[i][j] = dp[i - 1][j]; 
            } else {
                // 装入或不装入背包
                dp[i][j] = dp[i - 1][j] | dp[i - 1][j-nums[i-1]];
            }
        }
    }
    return dp[n][sum];
}

python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum=0
        for i in nums:
            sum+=i
        if sum %2 != 0:
            return False
        n=len(nums)
        sum=sum//2
        dp=[[False]*(sum+1) for i in range(n+1)]
        # print(dp)
        for i in range(n+1):
            dp[i][0]=True
        for i in range(1,n+1):
            for j in range(1,sum+1):
                if j-nums[i-1]<0:
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i-1]]
                    # dp[i][j]=dp[i-1][j] | dp[i-1][j-nums[i-1]]
        return dp[n][sum]

状态压缩：

注意: 

dp[i][j]都是通过上一行dp[i-1][..]转移过来的，之前的数据都不会再使用了。
dp[j]其实就相当于dp[i-1][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool canPartition(vector<int>& nums) {
    int sum = 0, n = nums.size();
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;
    sum = sum / 2;
    vector<bool> dp(sum + 1, false);
    // base case
    dp[0] = true;

    for (int i = 0; i < n; i++) 
        for (int j = sum; j >= 0; j--) 
            if (j - nums[i] >= 0) 
                dp[j] = dp[j] || dp[j - nums[i]];

    return dp[sum];
}

3、完全背包

518. 零钱兑换 II

链接：https://leetcode-cn.com/problems/coin-change-2/

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:

输入: amount = 10, coins = [10] 
输出: 1


注意:

你可以假设：

0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

思考：

有一个背包，最大容量为amount，有一系列物品coins，每个物品的重量为coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？

和01背包最大的区别就是，每个物品的数量是无限的，这也就是传说中的「完全背包问题」

第一步：

状态：「背包的容量」和「可选择的物品」
选择：「装进背包」或者「不装进背包」
1
2
3
4
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 计算(选择1，选择2...)

第二步：dp数组的定义

dp[i][j]的定义如下：

若只使用前i个物品，当背包容量为j时，有dp[i][j]种方法可以装满背包。
即只使用coins中的前i个硬币的面值，若想凑出金额j，有dp[i][j]种凑法。

base case 为dp[0][..] = 0， dp[..][0] = 1。因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为 0，那么“无为而治”就是唯一的一种凑法。

答案就是dp[N][amount]，其中N为coins数组的大小。

1
2
3
4
5
6
7
8
9
10
int dp[N+1][amount+1]
dp[0][..] = 0
dp[..][0] = 1

for i in [1..N]:
    for j in [1..amount]:
        把物品 i 装进背包,
        不把物品 i 装进背包
return dp[N][amount]

第三步：根据「选择」，思考状态转移的逻辑

特殊点：在于物品的数量是无限的

如果你不把这第i个物品装入背包，也就是说你不使用coins[i]这个面值的硬币，那么凑出面额j的方法数dp[i][j]应该等于dp[i-1][j]，继承之前的结果。

如果你把这第i个物品装入了背包，也就是说你使用coins[i]这个面值的硬币，那么dp[i][j]应该等于dp[i][j-coins[i-1]]。

首先由于i是从 1 开始的，所以coins的索引是i-1时表示第i个硬币的面值。

总结：

状态：硬币，金额
选择：当前硬币选或者不选

dp数组含义：dp[i][j]表示前i个硬币可以达到j金额的组合数

状态转移方程：dp[i][j]=dp[i−1][j]+dp[i][j−coins[i−1]]

注意：就是不选和选相加，选时的硬币下标仍为i，因为硬币个数无限，这个硬币上次仍然可以选；
     完全背包和01背包的唯一不同之处；

java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int change(int amount, int[] coins) {
    int n = coins.length;
    int[][] dp = amount int[n + 1][amount + 1];
    // base case
    for (int i = 0; i <= n; i++) 
        dp[i][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= amount; j++)
            if (j - coins[i-1] >= 0)
                dp[i][j] = dp[i - 1][j] 
                         + dp[i][j - coins[i-1]];
            else 
                dp[i][j] = dp[i - 1][j];
    }
    return dp[n][amount];
}

1
2
3
4
5
6
7
8
9
10
11
int change(int amount, int[] coins) {
    int n = coins.length;
    int[] dp = new int[amount + 1];
    dp[0] = 1; // base case
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= amount; j++)
            if (j - coins[i] >= 0)
                dp[j] = dp[j] + dp[j-coins[i]];

    return dp[amount];
}

python:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n=len(coins)
        dp=[[0]*(amount+1) for i in range(n+1)]
        for i in range(n+1):
            dp[i][0]=1
        for i in range(1,n+1):
            for j in range(1,amount+1):
                if j-coins[i-1]>=0:
                    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]]
                else:
                    dp[i][j]=dp[i-1][j]
        return dp[n][amount]

Posted on Edited on In

一、打家劫舍系列

解决动态规划问题就是找「状态」和「选择」，仅此而已。

假想你就是这个专业强盗，从左到右走过这一排房子，在每间房子前都有两种选择：抢或者不抢。

「状态」和「选择」：你面前房子的索引就是状态，抢和不抢就是选择。

198.打家劫舍

链接：https://leetcode-cn.com/problems/house-robber/

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

题解一|动态规划:

1、定义数组元素的含义
    数组nums:各个房间的现金
    数组flags：记录各个房间有没有被偷，若flag = 0 则没偷， flag = 1 则偷了。
    数组dp：dp[i]代表前i个房屋偷到的最大现金数
2、递推方程式
    1）只考虑前两个房间时，谁大选谁
    2）考虑第三个房间

        如果偷第三个房间，则意味着第二个房间不偷，也就是第三个房间值 + 第一个房间的宝藏数量；
        如果不偷第三个房间，则宝藏数量等于前两个房间宝藏数量；

    dp[i]=max(nums[i]+dp[i-2],dp[i-1])
3、初始值
第一个房间：

    Condistion 1 ：dp[0] = nums[0] ; flags[0] = 1;
    Condistion 2 ：dp[0] = 0; flags[0] = 0;

第二个房间：

    Condistion 1 ：when flags[1] = 1; dp[1] = nums[1];

    Condistion 2 ：when flags[1] = 0; dp[1] = dp[0];

    选 Condistion 1 还是 Condistion 2呢？比较 两种情况下dp[1]的大小推广到前i个房间: (i>=2)

    when flags[i] = 1, dp[i] = nums[i] + dp[i-2]
    when flags[i] = 0; dp[i] = dp[i-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def rob(self, nums: List[int]) -> int:
        lens=len(nums)
        if lens==0:
            return 0

        # flag=lens*[0]
        dp=lens*[0]

        dp[0]=nums[0]
        if lens<2:
            return dp[0]
        dp[1]=max(nums[0],nums[1])
        for i in range(2,lens):
            dp[i]=max(nums[i]+dp[i-2],dp[i-1])
    
        return dp[lens-1]

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)==0:
            return 0
        if len(nums)<=2:
            return max(nums)
        dp=[0]*2
        dp[0]=nums[0]
        dp[1]=max(nums[0],nums[1])
        for i in range(2,len(nums)):
            dp[i%2]=max(dp[(i-1)%2],dp[(i-2)%2]+nums[i])
        return max(dp) # return dp[(len(nums)-1)%2]

题解二|自顶向下|超时:

1
2
3
4
5
6
7
8
9
class Solution:
    def rob(self, nums: List[int]) -> int:
        return self.dp(nums,0)
    def dp(self,nums,start):
        if start >= len(nums):
            return 0
        # 不抢，去下家；抢，去下下家
        res=max(self.dp(nums,start+1),nums[start]+self.dp(nums,start+2))
        return res

使用备忘录进行优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def rob(self, nums: List[int]) -> int:
        # 初始化备忘录
        self.memo={}
        for i in range(len(nums)):
            self.memo[i]=-1

        return self.dp(nums,0)
    def dp(self,nums,start):
        if start >= len(nums):
            return 0
        # 避免重复计算
        if self.memo[start] != -1:
            return self.memo[start]
        # 不抢，去下家；抢，去下下家
        res=max(self.dp(nums,start+1),nums[start]+self.dp(nums,start+2))

        # 记入备忘录
        self.memo[start]=res
        return res

题解三|自顶向下的动态规划:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def rob(self, nums: List[int]) -> int:
        n=len(nums)
        if not nums:
            return 0
        if n<2:
            return nums[0]
        dp=[0]*(n)
        dp[0]=nums[0]
        dp[1]=max(nums[0],nums[1])
        for i in range(2,n):
            dp[i]=max(dp[i-1],nums[i]+dp[i-2])
        return dp[n-1]
1
2
3
4
5
6
7
8
9
10
11
int rob(int[] nums) {
    int n = nums.length;
    // dp[i] = x 表示：
    // 从第 i 间房子开始抢劫，最多能抢到的钱为 x
    // base case: dp[n] = 0
    int[] dp = new int[n + 2];
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
    }
    return dp[0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
int rob(int[] nums) {
    int n = nums.length;
    // 记录 dp[i+1] 和 dp[i+2]
    int dp_i_1 = 0, dp_i_2 = 0;
    // 记录 dp[i]
    int dp_i = 0; 
    for (int i = n - 1; i >= 0; i--) {
        dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i;
}

213. 打家劫舍 II

链接：https://leetcode-cn.com/problems/house-robber-ii/

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

题解一|动态规划：

思路：
    在 [0:n-1] 中找到最大值
    在 [1:n] 中找到最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rob(self, nums: List[int]) -> int:
        def helper(nums):
            if not nums:
                return 0
            n=len(nums)
            if n==1:
                return nums[0]
            dp=[0]*n
            dp[0]=nums[0]
            dp[1]=max(nums[0],nums[1])
            for i in range(2,n):
                dp[i]=max(dp[i-2]+nums[i],dp[i-1])
            return dp[-1]
        if not nums:
            return 0
        if len(nums)==1:
            return nums[0]
        return max(helper(nums[1:]),helper(nums[:len(nums)-1]))

题解二：

首尾房间不能同时被抢，那么只可能有三种不同情况：
    要么都不被抢；
    要么第一间房子被抢最后一间不抢；
    要么最后一间房子被抢第一间不抢。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(robRange(nums, 0, n - 2), 
                    robRange(nums, 1, n - 1));
}

// 仅计算闭区间 [start,end] 的最优结果
int robRange(int[] nums, int start, int end) {
    int n = nums.length;
    int dp_i_1 = 0, dp_i_2 = 0;
    int dp_i = 0;
    for (int i = end; i >= start; i--) {
        dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i;
}

337. 打家劫舍 III

链接：https://leetcode-cn.com/problems/house-robber-iii/

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

题解一|递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int rob(TreeNode root) {
    if (root == null) return 0;

    int money = root.val;
    if (root.left != null) {
        money += (rob(root.left.left) + rob(root.left.right));
    }

    if (root.right != null) {
        money += (rob(root.right.left) + rob(root.right.right));
    }

    return Math.max(money, rob(root.left) + rob(root.right));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rob(self, root: TreeNode) -> int:
        if not root:
            return 0
        money=root.val
        if root.left:
            money+=(self.rob(root.left.left)+self.rob(root.left.right))
        if root.right:
            money+=(self.rob(root.right.left)+self.rob(root.right.right))
        return max(money,self.rob(root.left)+self.rob(root.right))

题解二|memo记忆化递归：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rob(self, root: TreeNode) -> int:
        self.memo={}

        def helper(root):
            if not root:
                return 0
            if root in self.memo:
                return self.memo[root]
            money=root.val
            if root.left:
                money+=(helper(root.left.left)+helper(root.left.right))
            if root.right:
                money+=(helper(root.right.left)+helper(root.right.right))
            
            result=max(money,helper(root.left)+helper(root.right))
            self.memo[root]=result
            return result
        
        return helper(root)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int rob(TreeNode root) {
    HashMap<TreeNode, Integer> memo = new HashMap<>();
    return robInternal(root, memo);
}

public int robInternal(TreeNode root, HashMap<TreeNode, Integer> memo) {
    if (root == null) return 0;
    if (memo.containsKey(root)) return memo.get(root);
    int money = root.val;

    if (root.left != null) {
        money += (robInternal(root.left.left, memo) + robInternal(root.left.right, memo));
    }
    if (root.right != null) {
        money += (robInternal(root.right.left, memo) + robInternal(root.right.right, memo));
    }
    int result = Math.max(money, robInternal(root.left, memo) + robInternal(root.right, memo));
    memo.put(root, result);
    return result;
}

题解三：

每个节点可选择偷或者不偷两种状态，根据题目意思，相连节点不能一起偷

当前节点选择偷时，那么两个孩子节点就不能选择偷了
当前节点选择不偷时，两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)
我们使用一个大小为 2 的数组来表示 int[] res = new int[2] 0 代表不偷，1 代表偷
任何一个节点能偷到的最大钱的状态可以定义为

当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
当前节点选择偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
表示为公式如下

root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) + Math.max(rob(root.right)[0], rob(root.right)[1])

root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int rob(TreeNode root) {
    int[] result = robInternal(root);
    return Math.max(result[0], result[1]);
}

public int[] robInternal(TreeNode root) {
    if (root == null) return new int[2];
    int[] result = new int[2];

    int[] left = robInternal(root.left);
    int[] right = robInternal(root.right);

    result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    result[1] = left[0] + right[0] + root.val;

    return result;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Map<TreeNode, Integer> memo = new HashMap<>();
public int rob(TreeNode root) {
    if (root == null) return 0;
    // 利用备忘录消除重叠子问题
    if (memo.containsKey(root)) 
        return memo.get(root);
    // 抢，然后去下下家
    int do_it = root.val
        + (root.left == null ? 
            0 : rob(root.left.left) + rob(root.left.right))
        + (root.right == null ? 
            0 : rob(root.right.left) + rob(root.right.right));
    // 不抢，然后去下家
    int not_do = rob(root.left) + rob(root.right);

    int res = Math.max(do_it, not_do);
    memo.put(root, res);
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int rob(TreeNode root) {
    int[] res = dp(root);
    return Math.max(res[0], res[1]);
}

/* 返回一个大小为 2 的数组 arr
arr[0] 表示不抢 root 的话，得到的最大钱数
arr[1] 表示抢 root 的话，得到的最大钱数 */
int[] dp(TreeNode root) {
    if (root == null)
        return new int[]{0, 0};
    int[] left = dp(root.left);
    int[] right = dp(root.right);
    // 抢，下家就不能抢了
    int rob = root.val + left[0] + right[0];
    // 不抢，下家可抢可不抢，取决于收益大小
    int not_rob = Math.max(left[0], left[1])
                + Math.max(right[0], right[1]);

    return new int[]{not_rob, rob};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def rob(self, root: TreeNode) -> int:
        res=self.dp(root)
        return max(res[0],res[1])

    def dp(self,root):
        if not root:
            return (0,0)
        left=self.dp(root.left)
        right=self.dp(root.right)
        rob=root.val+left[0]+right[0]
        not_rob=max(left[0],left[1])+max(right[0],right[1])
        return (not_rob,rob)

Posted on Edited on In

一、股票买卖系列

1
2
3
4
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)

每天都有三种「选择」：买入、卖出、无操作，我们用 buy, sell, rest 表示这三种选择。

问题是，并不是每天都可以任意选择这三种选择的，因为 sell 必须在 buy 之后，buy 必须在 sell 之后（第一次除外）。那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。而且别忘了，我们还有交易次数 k 的限制，就是说你 buy 还只能在 k > 0 的前提下操作。

问题的「状态」有三个，第一个是天数，第二个是当天允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。

穷举：

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp5.jpg

dp[3][2][1]:今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。

dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。

最终所求：dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，所能获取的最大利润。

为什么不是 dp[n - 1][K][1]？因为 [1] 代表手上还持有股票，[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。

状态转移：
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp6.jpg

状态转移方程：

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp7.jpg

bad case:

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp8.jpg

总结：

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp9.jpg

121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题解一|暴力破解：

时间复杂度:O(n^2)
空间复杂度:O(1)

1
2
3
4
5
6
7
8
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit=0
        for i in range(len(prices)-1):
            for j in range(i+1,len(prices)):
                if prices[j]-prices[i] > profit:
                    profit=prices[j]-prices[i]           
        return profit

题解二：

时间复杂度:O(n)
空间复杂度:O(1)

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minPrice=float('inf')
        profit=0
        for i in range(len(prices)):
            if prices[i] < minPrice:
                minPrice=prices[i]
            elif prices[i]-minPrice > profit :
                profit=prices[i]-minPrice
        return profit

题解三：

时间复杂度:O(n)
空间复杂度:O(1)

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        profit=0
        tmp=prices[0]
        for i in range(1,len(prices)):
            tmp=min(tmp,prices[i])
            profit=max(profit,prices[i]-tmp)
        return profit

题解四|万能公式：

思路：
K=1

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp10.jpg

时间复杂度：O(n)
空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp=[[0]*2 for i in range(n)]
        for i in range(n):
            if i-1==-1:
                dp[i][0]=0
                # dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
                          =max(dp[-1][0],dp[-1][1]+prices[i])
                          =max(0,-float('inf')+prices[i])
                          =0
                dp[i][1]=-prices[i]
                # dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
                          =max(dp[-1][1],dp[-1][0]-prices)
                          =max(-float('inf'),0-prices)
                          =-prices
                continue
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1]=max(dp[i-1][1], -prices[i])
        # print(dp)
        return dp[n-1][0]

时间复杂度：O(n)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp_i_0=0  # dp[-1][0]=0
        dp_i_1=-float('inf') # dp[-1][1]=-float('inf')
        for i in range(n):
            dp_i_0=max(dp_i_0,dp_i_1+prices[i])
            dp_i_1=max(dp_i_1,-prices[i])
        return dp_i_0
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        n = len(prices)
        dp = [[0,0] for _ in range(n)]
        dp[-1][0] = 0
        dp[-1][1] = - float('inf')
        dp[0][0] = 0
        dp[0][1] = - float('inf')
        for i in range(n):
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]+ prices[i]) 
            dp[i][1] = max(dp[i-1][1],- prices[i])
        return dp[-1][0]

122. 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

思路：
K=+infinity

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp11.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp=[[0]*2 for i in range(n)]
        dp[-1][0]=0
        dp[-1][1]=-float('inf')
        dp[0][0]=0
        dp[0][1]=-float('inf')
        for i in range(n):
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
        return dp[n-1][0]

时间复杂度：O(n)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp_i_0=0
        dp_i_1=-float('inf')
        for i in range(n):
            tmp=dp_i_0
            dp_i_0=max(dp_i_0,dp_i_1+prices[i])
            dp_i_1=max(dp_i_1,tmp-prices[i])
        return dp_i_0

309. 最佳买卖股票时机含冷冻期

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

思路：
K=+infinity with cooldown
每次sell后要等一天才能继续交易；

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp12.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n=len(prices)
        if n == 0 or n==1:
            return 0
        dp=[[0]*2 for i in range(n)]
        dp[-1][0]=0
        dp[-1][1]=-float('inf')
        dp[-2][0]=0 # 不要这个初始值也可以，前面已经初始化。
        dp[0][0]=0
        dp[0][1]=-float('inf')
        for i in range(n):
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i])
        return dp[n-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        if len(prices) == 1: return 0
        n = len(prices)
        dp = [[0 for i in range(2)] for _ in range(n)]
        dp[-1][1] = -float('inf')
        dp[-2][1] = -float('inf')
        dp[0][1] = -float('inf')
        for i in range(n):
            dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
            dp[i][1] = max(dp[i-1][1],dp[i-2][0] - prices[i])
        return dp[-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        if len(prices) == 1: return 0
        n = len(prices)
        dp_i_0=0
        dp_i_1=-float('inf')
        dp_pre_0=0 # 代表dp[i-2][0]
        for i in range(n):
            tmp=dp_i_0
            dp_i_0=max(dp_i_0,dp_i_1+prices[i])
            dp_i_1=max(dp_i_1,dp_pre_0-prices[i])
            dp_pre_0=tmp
        return dp_i_0

714. 买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1:

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:

0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.

思路：

K=+infinity with fee
每次交易要支付手续费，只要把手续费从利润中减去即可；

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp13.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp=[[0]*2 for i in range(n)]
        dp[-1][0]=0
        dp[-1][1]=-float('inf')
        dp[0][0]=0
        dp[0][1]=-float('inf')
        for i in range(n):
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]-fee)
        return dp[n-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp_i_0=0
        dp_i_1=-float('inf')
        for i in range(n):
            tmp=dp_i_0
            dp_i_0=max(dp_i_0,dp_i_1+prices[i])
            dp_i_1=max(dp_i_1,tmp-prices[i]-fee)
        return dp_i_0

123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1] 
输出: 0 
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

思路：

K=2

k = 2 和前面题目的情况稍微不同，因为上面的情况都和 k 的关系不太大。要么 k 是正无穷，状态转移和 k 没关系了；要么 k = 1，跟 k = 0 这个 base case 挨得近，最后也被消掉了。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp14.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp=[[[0]*2 for i in range(3)] for i in range(n)]
        for k in range(3):
            dp[0][k][1]=-float('inf')
            dp[-1][k][1]=-float('inf')
        for i in range(n):
            for k in range(1,3):
                dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
                dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
        return dp[n-1][2][0]

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp15jpg

188. 买卖股票的最佳时机 IV

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

思路：

K=any integer

这题和 k = 2 没啥区别，可以直接套上一题的第一个解法。但是提交之后会出现一个超内存的错误，原来是传入的 k 值可以任意大，导致 dp 数组太大了。现在想想，交易次数 k 最多能有多大呢？

一次交易由买入和卖出构成，至少需要两天。所以说有效的限制次数 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        if k >= n//2:
            res=0
            for i in range(1,n):
                if prices[i] > prices[i-1]:
                    res += prices[i] - prices[i-1]
            return res
        else:
            dp=[[[0]*2 for i in range(k+1)] for i in range(n)]
            for t in range(k+1):
                dp[0][t][1]=-float('inf')
                dp[-1][t][1]=-float('inf')
            for i in range(n):
                for t in range(1,k+1):
                    dp[i][t][0]=max(dp[i-1][t][0],dp[i-1][t][1]+prices[i])
                    dp[i][t][1]=max(dp[i-1][t][1],dp[i-1][t-1][0]-prices[i])
            return dp[n-1][k][0]