发表更新刷题1 小时读完 (大约7193个字)

动态规划

【自顶向下】从一个规模较大的问题 f(20)，向下逐渐分解规模，直到 f(1)、f(2)触底，再逐层返回答案，这就是【自顶向下】

【自顶向上】直接从最低下，最简单，问题规模最小的f(1)和f(2)开始往上推，直到推到想要的答案f(20)，这就是动态规划的思路。

求解动态规划的核⼼问题是穷举。

  • 但是这类存在重叠子问题，直接暴力搜索效率较低。故需要一个备忘录或者DP Table，避免不必要的计算。

  • 其一定具备最优子结构，才能通过子问题的最值得到原问题的最值。

  • 由于问题千变万化，穷举所有可行解不不容易，故需要列出正确的状态转移方法。

重叠子问题，最优子结构，状态转移方程是动态规划的三要素。

写出状态转移方程一般是最难的，一个辅助框架：

明确 状态 -> 定义 dp数组/函数的含义 -> 明确 选择 -> 明确 base case。

摘自算法小抄

基本例子

斐波那契数列

1、暴力递归

1
2
3
def fib(N:int):
    if N == 1 or N == 2: return 1;
    return fib(N-1) + fib(N-2)

假设$N=20$，

image-20210809163431141

可以发现，这里存在大量的重复计算，既重叠子问题。

递归算法的时间复杂度：子问题个数 * 解决一个子问题需要的时间（函数中的操作）。

2、带备忘录的递归

既然耗时原因是超时，那就造一个备忘录，每次算一个子问题的值后，先将其存到备忘录中，再返回；每次遇到一个子问题先查询备忘录，看看有没有记录，再去做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def fib_with_not(N:int):

    note = [0]*(N+1) # 备忘录初始化为0

    def helper(n:int):
        if n == 1 or n == 2: return 1;
        # print("-->",n)
        # 如果已经计算过
        if note[n] != 0:
            return note[n]
        note[n] = helper(n-1) + helper(n-2)
        return note[n]
    res = helper(N)
    # print(note)
    return res

现在画出递归树，你就知道 备忘录 到底做了什么：

image-20210809170446436

实际上， 带「备忘录」 的递归算法， 把⼀棵存在巨量冗余的递归树通过「剪枝」 ， 改造成了⼀幅不存在冗余的递归图， 极⼤减少了⼦问题（即递归图中节点） 的个数。

image-20210809170947725

自顶向上与自顶向下

【自顶向下】从一个规模较大的问题 f(20)，向下逐渐分解规模，直到 f(1)、f(2)触底，再逐层返回答案，这就是【自顶向下】

【自顶向上】直接从最低下，最简单，问题规模最小的f(1)和f(2)开始往上推，直到推到想要的答案f(20)，这就是动态规划的思路。

3、dp数组的迭代解法

将备忘录独立出来，搞成dp_table，在其上完成【自底向上】。

1
2
3
4
5
6
7
8
def fib3(N:int):
    # 加1是为直接返回N
    dp_table = [0] *(N+1)
    # base case 
    dp_table[1] = dp_table[2] =1
    for i in range(3,N+1):
        dp_table[i] = dp_table[i-1] + dp_table[i-2]
    return dp_table[N]
image-20210809171835701

这⾥， 引出「状态转移⽅程」 这个名词， 实际上就是描述问题结构的数学形式：

image-20210809171919422

「状态转移⽅程」 的重要性， 它是解决问题的核⼼。 很容易发现， 其实状态转移⽅程直接代表着暴⼒解法。

凑零钱问题

给你 k 种⾯值的硬币， ⾯值分别为 c1, c2 ... ck ， 每种硬币的数量⽆限， 再给⼀个总⾦额 amount ， 问你最少需要⼏枚硬币凑出这个⾦额， 如果不可能凑出， 算法返回 -1 。函数签名如下：

1
2
# coins 代表可选面值，amount是目标金额
def coinChange(coins:list, amount:int)

⽐如说 k = 3 ， ⾯值分别为 1， 2， 5， 总⾦额 amount = 11 。 那么最少需要 3 枚硬币凑出， 即 11 = 5 + 5 + 1。

1、暴力递归

什么是最优子结构？

假如问题是考出最高的总成绩，那么你只需要每门课考到最好，每门课之间互不影响。

但是如果加一个条件，你的语文和数学成绩会相互制约，此消彼长。这样你考的总分就不是最高的了。因为子问题并不独立，无法同时最优，所以最优子结构被破坏。

回到这一题，如你想求amount=11的最少硬币数，你可以先求amount=10的最少硬币数（子问题），你只需要把子问题的答案加一就是原问题的答案。

先确定【状态】，既原问题和子问题之间变化的量，由于硬币数量无限，故唯一的状态就是目标金额amount。

确定【dp函数】的定义，当前目标金额是n，至少需要dp(n)个硬币凑出该金额。

然后确定【选择】并择优，既对于每个状态，可以做出什么选择改变当前状态。

体到这个问题， ⽆论当前的⽬标⾦额是多少， 选择就是从⾯额列表coins 中选择⼀个硬币， 然后⽬标⾦额就会减少。

代码框架：

1
2
3
4
5
6
7
8
def coinChange(coins:list, amount:int):
    
    def dp(n):
        for coin in coins:
            res = min(res,1+dp(n-coin))
           
        return res
   	return dp(amount)

最后明确【base case】，显然目标金额为0时，所需硬币为0；当目标金额小于0时，无解，返回-1；

1
2
3
4
5
6
7
8
9
10
11
12
def coinChange(coins:list, amount:int):
    
    def dp(n):
        if n == 0: return 0
        if n < 0: return -1
        res = float('inf')
        for coin in coins:
            subproblem = dp(n-coin)
            res = min(res,1+subproblem)
           
        return res if res != float('inf') else -1
   	return dp(amount)

以上代码的数学形式就是状态转移方程：

image-20210809194540915

2、带备忘录的递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def coinChange2(self, coins: list, amount: int) -> int:
    memo = dict()
    def dp(n):
        if n in memo: return memo[n]
        if n == 0: return 0
        if n < 0: return -1
        res = float('inf')
        for coin in coins:
            subproblem = dp(n-coin)
            if subproblem == -1: continue
            res = min(res,1+subproblem)
        
        # 计入备忘录
        memo[n] = res if res != float('inf') else -1
        return memo[n] 
    return dp(amount)

3、dp数组的迭代解法

定义dp数组：

dp[i]=x表示，当目标金额为i时，至少需要x枚硬币。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 相当于初始化为正无穷，便于比较
        dp = [amount+1] * (amount+1) # dp[i] =x 表示 目标金额为i时，至少需要x枚货币
        # base case
        dp[0] = 0
        # 目标金额作为变量，枚举
        for i in range(len(dp)):

            for coin in coins: # 对当前金额分别枚举不同的硬币
                # 子问题无解
                if i - coin < 0:
                    continue
                dp[i] = min(dp[i],1 + dp[i-coin]) # 当前的子问题依赖前一个子问题，
                
        return -1 if dp[amount] == amount + 1 else dp[amount]

NC19 子数组的最大累加和问题

分析

定义dp数组的含义：

**以nums[i]为结尾的「最大子数组和」为dp[i]**。

这种定义之下，想得到整个nums数组的「最大子数组和」，不能直接返回dp[n-1]，而需要遍历整个dp数组：

1
2
3
4
5
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
    res = Math.max(res, dp[i]);
}
return res;

依然使用数学归纳法来找状态转移关系：假设我们已经算出了dp[i-1]，如何推导出dp[i]呢？

可以做到，dp[i]有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。

如何选择？既然要求「最大子数组和」，当然选择结果更大的那个：

1
2
// 要么自成一派，要么和前面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxsumofSubarray(self , arr ):
        n = len(arr)
        if n == 0:
            return 0
        
        dp = [0] *n
        dp[0] = arr[0] # 第一个元素前没有子数组
        # print(a)
        # 状态转移方程
        for i in range(1,n):
            dp[i] = max(dp[i-1]+arr[i],arr[i])

        sum_max = float("-inf")
        print(dp)
        for i in range(n):
            sum_max = max(sum_max,dp[i])
        # print(max)
        return sum_max

NC7 买卖股票的最好时机

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxProfit2(self , prices ):
        '''
        暴力法
        '''
        # write code here
        n = len(prices)
        g_max = 0
        for i in range(n):
            for j in range(i+1,n):
                cur_max = prices[j] - prices[i]
                g_max = max(cur_max,g_max)


        return g_max

一次遍历

1
2
3
4
5
6
7
8
9
10
def maxProfit(self,prices ):
    g_max = 0
    curMin = prices[0] # 找全局的最小值
    n = len(prices) # 找全局的最大值
    # 固定sell，找买入
    for sell in range(1,n):
        curMin = min(curMin,prices[sell])
        g_max = max(g_max, prices[sell] - curMin)
    return g_max

NC34 求路径

分析

机器人有两个约束条件：

  • 机器人每次只能往右或者往下走
  • 机器人不能越界

定义DP数组

二维dp数组，dp[i] [j] 表示从起点到我当前位置（i行j列）有多少条可行的路径，因为我们从约束条件中可以知道，机器人每次只能往右或者往下走，则我们当前点必定是从上面或者左边走过来的（除边界外）。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def uniquePaths(self , m , n ):
        # write code here
        dp = [
        [0 for _ in range(n)]
            for _ in range(m)]
        dp[0][0]= 1
        for row in range(m):
            for col in range(n):
                if row > 0 and col > 0:
                    dp[row][col] = dp[row-1][col] + dp[row][col-1]
                # TODO 边界情况
                elif row == 0 and col>0:
                    dp[row][col] = dp[row][col-1]
                # TODO 边界情况
                elif row > 0 and col ==0:
                    dp[row][col] = dp[row-1][col]
        return dp[m-1][n-1]

NC126 换钱的最少货币数

描述

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。

如果无解，请返回-1.

解法

定义dp数组：dp[i]=x表示，当目标金额为i时，至少需要x枚硬币。

回到这一题，如你想求amount=11的最少硬币数，你可以先求amount=10的最少硬币数（子问题），你只需要把子问题的答案加一就是原问题的答案。

加1指的是，用当前面额的硬币可以凑出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minMoney(self , arr , aim ):
        dp = [aim+1] * (aim+1) # 相当于正无穷
        dp[0] = 0
        coins = sorted(arr)
        
        for cur_money in range(len(dp)):
            for coin in coins:
                # 子问题无解
                if cur_money-coin < 0:
                    continue

                dp[cur_money] = min(dp[cur_money],1 + dp[cur_money-coin])
        return -1 if dp[aim] == aim+1 else dp[aim]

NC145 0-1背包

描述

已知一个背包最多能容纳物体的体积为 img

现有 img 个物品，第 img 个物品的体积为$ v_i$​ , 重量为 $w_i$。

求当前背包最多能装多大重量的物品?

解法

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

第一步要明确两点，「状态」和「选择」。

状态有两个，就是「背包的容量」和「可选择的物品」。

选择就是「装进背包」或者「不装进背包」。

明白了状态和选择，动态规划问题基本上就解决了，只要往这个框架套就完事儿了：

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

第二步要明确dp数组的定义。

dp数组是什么？其实就是描述问题局面的一个数组。换句话说，我们刚才明确问题有什么「状态」，现在需要用dp数组把状态表示出来。

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

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

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

根据这个定义，我们想求的最终答案就是dp[N][W]。

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

细化上面的框架：

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]

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

简单说就是，上面伪码中「把物品i装进背包」和「不把物品i装进背包」怎么用代码体现出来呢？

这一步要结合对dp数组的定义和我们的算法逻辑来分析：

先重申一下刚才我们的dp数组的定义：

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]。

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

从1开始，对应的物品是0。

而dp[i-1][w-wt[i-1]]也很好理解：你如果想装第i个物品，你怎么计算这时候的最大价值？

w是当前背包的容量，wt[i-1]是第i个物品的重量，val[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]

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def knapsack(self , V , n , vw ):
        # write code here
        dp = [[0 for _ in range(V+1)] for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, V+1):
                if j < vw[i-1][0]:
                    dp[i][j] = dp[i-1][j]        # 当前体积不装第i个物品
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-vw[i-1][0]]+vw[i-1][1])
                    # # 当前体积不装第i个物品 或者 之前的体积+新装物体的价值
        return dp[n][V]

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];
}

NC148 几步可以从头跳到尾

描述

动态规划

来自牛客题解区

使用 dp[i] 表示第 i 个元素到最后一个元素所需要的步数（下标从1开始），起点是 n-1 到 n 需要步数为1，依次自定向下计算：

  • 对于第 $i$个元素，如果 $i + A[i-1] \geq n$ （数组下标从0开始），则可以一步到位；
  • 否则我们遍历 $i$ 之后的元素，找到最小到$n$的步数，既 $dp[i] = min(dp[i+j],d[i])$​，（j为往后遍历的数量），并使之加一
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
class Solution:
    def Jump(self , n , A ):
        # write code here
        # TODO 使用 `dp[i]` 表示第 `i` 个元素到最后一个元素所需要的步数
        dp = [n+1]*(n+1) # n+1 代表正无穷
        # 排除一步到位
        if 1 + A[0] >= n:
            return 1
        dp[n-1] = 1 # 第n-1个格子到第n个格子的步数一定为1
        for i in range(n-2,0,-1):
            print("i->",i)
            # TODO 在当前位置可以一步到底
            if i + A[i-1] >= n:
                dp[i] = 1
                continue
            
            
            for j in range(1,A[i-1]+1):
                dp[i] = min(dp[i+j],dp[i])

            '''
            由于是从后向前遍历，前一步到后一步需要+1
            '''
            dp[i] += 1
        print(dp)
        return dp[1]

动态规划2

从前向后找跳板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def Jump2(self,n,A):
    dp = [n+1] * (n)
    # TODO dp[i] 定义 从起点到达位置i需要几步，起点从0开始
    dp[0] = 0

    for i in range(0,n):
        cur_max = i + A[i]
        j = i + 1

        # j 是以i为跳板一步可以到达的位置
        while j<= cur_max and j <n:
            dp[j] = min(dp[i]+1,dp[j])
            j += 1
    # print(dp)
    return dp[n-1]

动态规划3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def Jump3(self,n,A):
    # TODO 表示到达第i个节点，至少需要多少个元素
    dp = [0] * (n+1)

    i,j = 2,1 # j 代表 i的前一个元素
    while i<=n:
        
        # TODO 相当于找到前一个元素能到达的最大位置吗，i相当于距离
        # 大于说明，从j这个位置可以跳到i
        # 小于说明，从j这个位置跳不到i，需要向前走一步
        while j + A[j-1] < i:
            j += 1
        
        dp[i] = dp[j] + 1 # TODO dp i 可以通过dp j 跳一步到达
        i += 1

贪心算法

摘自牛客评论区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def greedy(self,n,A):
    '''
    贪心算法
    '''
    end = 0 # 记录当前位置
    farthest = 0 # 最远位置
    steps = 0 # 跳跃次数
    len_ = n-1

    for i in range(len_):
        print(end,farthest)
        farthest = max(farthest,i+A[i]) # 计算在每个位置上可以跳跃的最远位置

        if end >= n:
            break
        
        # 如果当前位置和历史上最远的位置相同，说明真正的跳到了这里
        # 在这个位置进行下一次跳跃
        if end == i:
            end = farthest
            steps+=1
    return steps

NC155 牛牛的数列

摘自牛客评论区

牛牛现在有一个 n 个数组成的数列 nums , 牛牛现在想取一个连续的子序列,并且这个子序列还必须得满足: 最多只把一个数改变成一个正整数, 就可以使得这个连续的子序列是一个严格上升的子序列, 牛牛想知道这个连续子序列最长的长度是多少。

分析

tail[i] 表示以i结尾的最长连续递增子序列的长度，

head[i]表示以i开头的最长连续递增子序列的长度

状态转移方程，

对于tail[i]，初始状态tails[0]=1,如果 nums[i]大于nums[i-1]，则tail[i] = tail[i-1]+1,从左往右遍历

对于head[i]，初始状态head[n-1]=1，如果nums[i]小于nums[i+1]，则head[i] = head[i+1] +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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution:
    def maxSubArrayLength(self , nums ):
        # if nums == sorted(nums):
        #     return len(nums)
        n = len(nums) 
        if n<=2:
            return n

        head = [0] * n # 以 head[i] 开始的 最长连续上升子序列
        tail = [0] * n # 以 tail[i] 结尾的 最长连续上升子序列

        tail[0] = 1

        # 从左往右找出 连续的子序列, 容易忽略后面的信息
        for i in range(1,n):
            # 后一个比前一个大，说明是连续的
            if nums[i]>nums[i-1]:
                tail[i] = tail[i-1] + 1
            else:
                tail[i] = 1 # 在当前位置不连续
        
        
        # 最后一位自己跟自己连续，容易忽略前面的信息
        head[n-1] = 1 
        # 从右向左找出 连续的子序列
        for i in range(n-1,-1,-1):
            # 如果后一个比前一个大，说明前面和后面是连续的
            if nums[i] > nums[i-1]:
                head[i-1] = head[i] + 1
            else:
                head[i-1] = 1 

        # print(tail)
        # print(head)

        # 最终结果
        res = 1
        for i in range(n):
            # 可以使用的连接点，连接点修改后可以得到更长连续的子序列
            if i-1>=0 and i+1 < n and nums[i+1]-nums[i-1]>1:
                res = max(res,tail[i-1]+head[i+1]+1)
            else:
                # 如果不满足，找单边长度
                if i == 0:
                    if nums[i+1] > 1: # 大于1说明，在i=0时可以修改一位来获得增加
                        res = max(res,head[i+1]+1)
                    else:
                        res = max(res,head[i+1])
                elif i == n-1:
                    res = max(res,tail[i-1]+1)
                else:
                    res = max(res,tail[i-1]+1,head[i+1]+1)

        return res

NC127 最长公共字串

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

解法：暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        len1 = len(str1)
        len2 = len(str2)
        if len1 < len2:
            min_len = len1
            min_str = str1
            max_str = str2
        else:
            min_len = len2
            min_str = str2
            max_str = str1
        global_max_str = ""
        for i in range(min_len-1,-1,-1):
            for j in range(i,min_len):
                cur_str = min_str[i:j+1]
                if cur_str in max_str:
                    if len(global_max_str) < len(cur_str):
                        global_max_str = cur_str
                print(str2[i:j+1])
        return global_max_str

解法：动态规划

参考评论区：

【数据结构和算法】动态规划解最长公共子串_牛客博客 (nowcoder.net)

注意这题求的是最长公共子串，不是最长公共子序列，子序列可以是不连续的，但子串一定是连续的。

定义 dp[i][j] 表示字符串 str1中的第 i个字符和 str2中 第 j 个字符为最后一个元素所构成的最长公共字串。

如果要求 dp[i][j]，也就是 str1的第 i 个字符和str2的第j个字符为最后一个元素所构成的最长公共字串，我们首先需要判断这两个字符是否相等。

  • 如果不相等，那么他们就不能构成公共字串，也就是

    dp[i][j]=0

  • 如果相等，我们还需要计算前面相等字符的个数，其实就是 dp[i-1][j-1]，所有

    dp[i][j]=dp[i-1][j-1]+1

其重点是，以i，j分别是str1，str2的结束字符串，当前的结尾字符记录，会在前一个字符记录上进行迭代，同时在迭代过程中记录字串长度，并记住结束位置

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
class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        maxLength = 0
        maxLastIndex = 0 # 记录最长公共字串最后一个元素在字符串str1中的位置
        len1 = len(str1)
        len2 = len(str2)

        dp = [
            [0 for _ in range(len2+1)]
            for _ in range(len1+1)
        ]

        for i in range(len1):
            for j in range(len2):

                # 递推公式，两个字符相等的情况
                if str1[i] == str2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1

                    # 如果遇到了更长的字串，要更新，记录最长字串的长度
                    if dp[i+1][j+1] > maxLength:
                        maxLength = dp[i+1][j+1]
                        maxLastIndex = i
                else:
                    dp[i+1][j+1] = 0 # 递推公式，两个字符不相等的情况
        
        # 对字符串进行截取
        res = str1[maxLastIndex-maxLength+1:maxLastIndex+1]
        return res

解法二：优化

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
maxLastIndex = 0  # 
maxLength = 0 # 记录最长公共字串的长度
len1 = len(str1)
len2 = len(str2)

dp = [0 for _ in range(len2+1)]

# print("--")
for i in range(0,len1):
    for j in range(len2-1,-1,-1):
      
        if str1[i] == str2[j]:
            # print(
            dp[j+1] = dp[j] + 1
            # print(i,j,dp[j],dp[j+1])
            
            if dp[j+1] > maxLength:
                maxLength = dp[j+1]
                maxLastIndex = i
        else:
            # 如果存在间隔会在这里置为0
            dp[j+1] = 0  # 递推公式，两个字符不相等的情
# print("---")
# print(dp)
res = str1[maxLastIndex-maxLength+1:maxLastIndex+1]
return res

NC91 最长递增子序列

描述

给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）

示例：

1
2
输入：[2,1,5,3,6,4,8,9,7]
返回值：[1,3,4,8,9]

解法：动态规划

来自评论区

题解 | #最长递增子序列#_牛客博客 (nowcoder.net)

dp[i]=x 意义为 以i为结尾的序列，最大递增子长度是多少。

比较顺序如下：

i j_border i->j
1 1 0
2 2 0,1
3 3 0,1,2
… … …
6 6 0,1,2,3,4,5

6号位置上的元素会依次与0-5号位置上的元素进行比较，如果6号位置上的元素大于0号位置上的元素，则dp[6]=dp[0]+1。

1
dp[i] = dp[j] + 1, if arr[i] > arr[j], j = 0,..., i-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 LIS(self , arr ):
        # write code here
        len_arr = len(arr)

        dp = [1] *(len_arr+1)
        g_max = 0 # 保存全局最长的序列长度
        for i in range(len_arr):
            for j in range(i):
                # print(i,j)
                if arr[i] > arr[j] and dp[i]<dp[j]+1:
                    dp[i] = dp[j] + 1 # i点比j点大，理论上要加一
                    g_max = max(g_max,dp[i])
        # print(dp)
        res = [0] * (g_max)
        dp_size = len_arr + 1
        i = dp_size-1
        j = g_max
        # 从后向前找
        while j >0:
            # 该点的长度恰好等于res的第j位，即找到了
            if dp[i] == j:
                j -=1 
                res[j] =arr[i]
            
            i -= 1
        return res

优化版：二分法动态规划

TY78 最大上升子序列

描述

链接：https://www.nowcoder.com/questionTerminal/dcb97b18715141599b64dbdb8cdea3bd?answerType=1&f=discussion
来源：牛客网

一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …,aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和. 你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)。

解法：来自评论区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
size_n = int(input().strip())
nums = list(map(int,input().strip().split()))

dp = [0]*(size_n+1) # 以arr[i]为结尾的最大上升子序列和
# print(dp)

g_max = 0


for i in range(size_n):
    dp[i] = nums[i] # 每个子序列都是它本身

    for j in range(i):
        # 如果当前值大于前一个值
        if nums[i] > nums[j]:
            # 如果前一个子序列的值加上当前值，和当前值进行比较
            dp[i] = max(dp[i], dp[j] + nums[i])
    g_max = max(g_max,dp[i])
    
# print(dp)
print(g_max)

2021网易测试开发-第6题

描述

大富翁游戏规则如下

  1. 玩家起始会获得一定资本M金币
  2. 玩家每一次可以走一个格，或者跳两个格；走一格耗费2个金币能量；跳两个格，耗费3个金币能量；金币只有满足能量消耗时，才能继续往下走
  3. 玩家每走到一个格，会得到这个格的奖励，每个格的奖励金币数为非负整数
  4. 当玩家走到这个格后，总金币数不足以支持下一步金币消耗时，则不能继续往下走，游戏结束
  5. 玩家第一步可以选择走一步进第1格或者跳2步进第2格起始，玩家可以选择在任意一格结束游戏

问玩家游戏中，最多能得到多少个金币？

分析

创建数组 dp，dp[i]代表在第i个位置可以获得的最大收益，i 从1开始直到结束。

第0个位置为初始成本。

在第i个位置的收益，dp[i] 等于跳过去的位置的收益dp[i-j-1] 加上当前位置的收益golds[i-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
28
29
def test4():
    M = int(input()) # 货架长度，每一层最多摆两个商品
    golds = list(map(int,input().split())) # 商品长度
    step_costs = [2,3]
    n = len(golds)
    dp = [0] * (n+1)
    dp[0] = M
    gold = 0
    # print("--")
    for i in range(1,n+1):
        for j,cur_cost in enumerate(step_costs):
            

            if i -j-1 <0:
                continue
            # 当前位置的收益不能撑起此次跳跃
            if dp[i-j-1] < cur_cost:
                continue
            # print(i,j,dp[i],dp[i-j-1])
            dp[i] = max(dp[i],dp[i-j-1] + golds[i-1] - cur_cost)
            # print("i: {}, j: {}, prev: {}, now: {}".format(i,j,dp[i-j-1],dp[i]))

        gold = max(gold,dp[i]) # 保留历史的最大收益

    # print(dp)
    gein = max(dp[1:])

    # print(gold)
    print(gein)

70. 爬楼梯

描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

1
2
3
4
5
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
1
2
3
4
5
6
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解法：

思想：dp[i]=dp[i-1]+dp[i-2]，和废弃那波数列有点像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    # 递归
    def climbStairs1(self, n: int) -> int:
        if n > 2:
            return self.climbStairs(n-2) + self.climbStairs(n-1)
        else:
            return n
        
    def climbStairs(self,n) -> int:
        dp = [0] * (n+1)
        
        dp[1] = 1 # 爬第一个台阶有1种
        dp[2] = 2 # 爬第2个台阶有两种

        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

动态规划

http://example.com/2021/08/09/动态规划/

作者

bd160jbgm

发布于

2021-08-09

更新于

2021-09-14

许可协议

#

喜欢这篇文章？打赏一下作者吧

关注我

链接

分类

最新文章

标签

BFS3
DFS3
Java面经1
algorithm4
android1
bfs2
c++9
dfs7
dp1
dpLearning13
java1
jvm9
ordered-map1
python8
spring6
sql3
tools16
二分查找1
二叉树13
位运算10
傻屌题1
分治2
分治算法2
动态规划6
双指针7
哈希1
哈希表2
回溯5
堆2
堆排序1
多线程1
字符串5
总结1
找规律2
指针1
排序9
数字1
数据库1
数组9
最短路径1
查找2
栈9
树12
测试6
测试知识1
滑动窗口1
自动机1
计算机基础2
计算机网络1
计算机网络基础1
论文阅读10
设计1
贪心算法3
较难13
递归6
链表14
队列1
需要review8
面试记录1
×