精华内容
下载资源
问答
  • 自底向上的语法分析

    2021-05-10 22:55:58
    从分析树的底部(叶节点向顶部根节点方向构造分析...可以看成是将输入串归约为文法开始符号S的过程【顶向下的语法分析采用最左推导方式自底向上的语法分析采用最左归约方式(反向构造最右推导)】 每次规约“句柄” ...


    参考哈工大课件

    自底向上的语法分析

    从分析树的底部(叶节点向顶部根节点方向构造分析树,可以看成是将输入串归约为文法开始符号S的过程

    自顶向下的语法分析采用最左推导方式;
    自底向上的语法分析采用最左归约方式,实际上是 反向构造最右推导

    自底向上语法分析的通用框架:移入-归约分析

    1)在对输入串的一次从左到右扫描过程中,语法分析器将零个或多个输入符号移入到栈的顶端,直到它可以对栈顶的一个文法符号串β进行归约为止
    2)它将β归约为某个产生式的左部
    3)语法分析器不断地重复这个循环,直到它检测到一个语法错误,或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时,语法分析器停止运行,并宣称成功完成了语法分析)为止
    注意:每步规约都是规范规约,每次规约“句柄”
    移入-归约分析器可采取的4种动作:

    • 移入:将下一个输入符号移到栈的顶端
    • 归约:被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端,并决定用哪个非终结符来替换这个串
    • 接收:宣布语法分析过程成功完成
    • 报错:发现一个语法错误,并调用错误恢复子例程

    移入-归约分析中存在的问题
    造成错误的原因:错误地识别了句柄

    LR分析法概述

    LR文法是最大的、可以构造出相应移入-归约语法分析器的文法类

    L: 对输入进行从左到右的扫描
    R: 反向构造出一个最右推导序列
    LR(k)分析:需要向前查看k个输入符号的LR分析。当省略(k)时,表示k =1

    1. LR 分析法的基本原理
      自底向上分析的关键问题是:如何正确地识别句柄。
      句柄是逐步形成的,用“状态”表示句柄识别的进展程度
      LR分析器基于这样一些状态来 构造自动机进行句柄的识别

    例:S→bBB
    S→·bBB 移进状态
    S→b·BB / S→bB·B 移进、待归约状态
    S→bBB· 归约状态
    注意: 产生式A→ε 只生成一个项目A→ ·

    1. LR 分析器(自动机)的总体结构
      在这里插入图片描述
      LR 分析表的结构:
    • sn:将符号a、状态n 压入栈
    • rn:用第n个产生式进行归约

    例:文法
    ① S→BB
    ② B→aB
    ③ B→b
    在这里插入图片描述

    输入bab#

    状态剩余输入动作
    0#bab#
    04#bab#0和b比较s4,移入b,添加4
    02#Bab#4和a比较r3,归约文法B→b右部长度1,在符号栈和状态栈中分别移出1个符号,在符号栈中进入B。此时栈顶是0,遇到刚规约出的B,到状态2,添加2状态
    023#Bab#2和a比较s3,移入a,添加3
    0234#Bab#3和b比较s4,移入b,添加4
    0236#BaB#4和#r3,归约文法B→b,4和b出栈,B进栈。3和B比较到状态6,6进栈
    025#BB#6和#比较r2,B→aB,36、aB出栈B进栈。2和B到到状态5,5入栈
    0#S#5和#比较r1,S→BB,25、BB出栈,S入栈。
    01#S#0和S比较到状态1,1入栈
    1遇到#成功接收acc
    • 如果ACTION[sm , ai]=acc,那么分析成功
    • 如果ACTION[sm , ai]=err ,那么出现语法错误
    //LR 分析算法
    输入:串w和LR语法分析表,该表描述了文法G的ACTION函数和GOTO函数。
    输出:如果w在 L(G)中,则输出w的自底向上语法分析过程中的归约步骤;否则给出一个错误指示。
    方法:初始时,语法分析器栈中的内容为初始状态s0,输入缓冲区中的内容为w#。
    令a为w$的第一个符号;
    while(1) { /* 永远重复*/ 
      令s是栈顶的状态;
      if ( ACTION [s,a] = st ) {
        将t压入栈中;
        令a为下一个输入符号;
      } else if (ACTION [s,a] =归约A → β ) {
        从栈中弹出│ β │个符号;
        将GOTO [t,A]压入栈中;
        输出产生式 A → β ;
      } else if (ACTION [s,a] =接受) 
          break/* 语法分析完成*/
       else调用错误恢复例程;
    }
    

    LR(0)分析

    增广文法:如果G 是一个以S为开始符号的文法,则G的增广文法 G’ 就是在G中加上新开始符号S’ 和产生式S’ → S而得到的文法
    引入增广文法的目的:使新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边,从而使得分析器只有一个接受状态
    可以把等价的项目组成一个项目集( I ) ,称为项目集闭包(Closure of Item Sets),每个项目集闭包对应着自动机的一个状态
    在这里插入图片描述

    CLOSURE()函数

    计算给定项目集I的闭包:

    CLOSURE(I) = I∪{B→ · γ | A→α·Bβ∈CLOSURE(I) , B→γ∈P}

    //CLOSURE()函数
    SetOfltems CLOSURE ( I ) {
      J = I;
      repeat
        for ( J中的每个项A → α·Bβ ) 
           for ( G的每个产生式B → γ ) 
             if ( 项B → · γ不在J中 ) 
                将B → · γ加入J中;
      until 在某一轮中没有新的项被加入到J中;
      return J;
    }
    

    LR(0) 分析过程中的冲突:移进/归约冲突& 归约归约冲突
    在这里插入图片描述
    表达式文法的LR(0)分析表含有移进/归约冲突
    在这里插入图片描述
    如果LR(0)分析表中没有语法分析动作冲突,那么给定的文法就称为LR(0)文法

    • 不是所有CFG都能用LR(0)方法进行分析,也就是说,CFG不总是LR(0)文法

    SLR分析

    在这里插入图片描述

    在状态2,使用LR0文法,不向后看符号,即不考虑上下文。由followE可以知道如果下一个符号是*,则采取移进,则不会产生冲突。

    SLR分析法的基本思想
    如果集合{a1, a2, …, am}和FOLLOW(B1), FOLLOW(B2),…,FOLLOW(Bn)两两不相交,则项目集I中的冲突可以按以下原则解决:

    • 设a是下一个输入符号
      若a∈{ a1, a2, …, am },则移进a;
      若a∈FOLLOW(Bi),则用产生式Bi→γi 归约
      此外,报错

    由此就可以化解冲突,如果能够化解冲突则成为SLR文法。
    在这里插入图片描述
    在这里插入图片描述
    只对于在follow集中的符号才进行归约

    //SLR 分析表构造算法
    构造G'的规范LR(0)项集族C = { I0, I1,, In}。
    根据Ii构造得到状态i。状态i 的语法分析动作按照下面的方法决定:
      if A→α·aβ∈Ii and GOTO( Ii , a )=Ij then ACTION[ i, a ]=sj
      if A→α.Bβ∈Ii and GOTO( Ii , B )=Ij then GOTO[ i, B ]=j
      if A→α·∈Ii且A ≠ S' then for a∈FOLLOW(A) do
    ACTION[ i, a ]=rj (j是产生式A→α的编号)
      if S'→S·∈Ii then ACTION [ i , $ ]=acc;
    没有定义的所有条目都设置为“error”。
    

    SLR分析存在的问题:
    SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A),但b∈FOLLOW(A)
    只是归约α的一个必要条件,而非充分条件

    LR(1)分析

    对于产生式 A→α的归约,在不同的使用位置,A会要求不同的后继符号。在特定位置,A的后继符集合是FOLLOW(A)的子集。
    规范LR(1)项目:
    将一般形式为 [A→α·β, a]的项称为 LR(1) 项,其中A→αβ 是一个产生式,a 是一个终结符(这里将$视为一个特殊的终结符)
    它表示在当前状态下,A后面必须紧跟的终结符,称为该项的展望符(lookahead)

    • LR(1) 中的1指的是项的第二个分量的长度
    • 在形如[A→α·β, a]且β ≠ ε的项中,展望符a没有任何作用
    • 但是一个形如[A→α·, a]的项在只有在下一个输入符号等于a时才可以按照A→α 进行归约。这样的a的集合总是FOLLOW(A)的子集,而且它通常是一个真子集。
      在这里插入图片描述
      在这里插入图片描述
    展开全文
  • 动态规划顶而下与自底而上(递归) 参考labuladong算法 动态规划特点: 1 . 重叠子问题 2.状态转移方程 3.最优子结构 一般题目有上面三个特点基本就是动态规划了,主要是求最值,做题的核心是学会穷举,而好的...

    动态规划自顶而下与自底而上(递归)

    参考labuladong算法

    动态规划特点:
    1 . 重叠子问题
    2.状态转移方程
    3.最优子结构
    一般题目有上面三个特点基本就是动态规划了,主要是求最值,做题的核心是学会穷举,而好的算法是教我们学会更”聪明“的穷举。

    1

    动态规划解法代码框架:
    
    // 
    #初始化(base case)
    dp[0][0][...] = base
    #进行状态转移
    for 状态1 in 状态 1 的所有值:
    	for 状态2 in 状态2 的所有值:
    		for ...  
    			dp[状态1][状态2][...] = 求最值 (选择1,选择2...

    下来我们来看Leetcode322,题目为:
    零钱兑换

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

    样例如下:
    
    // An highlighted block
    var foo = 'bar';
    j示例 1:
    
    输入:coins = [1, 2, 5], amount = 11
    输出:3 
    解释:11 = 5 + 5 + 1
    示例 2:
    
    输入:coins = [2], amount = 3
    输出:-1
    示例 3:
    
    输入:coins = [1], amount = 0
    输出:0
    示例 4:
    
    输入:coins = [1], amount = 1
    输出:1
    示例 5:
    
    输入:coins = [1], amount = 2
    输出:2
     
    
    提示:
    
    1 <= coins.length <= 12
    1 <= coins[i] <= 231 - 1
    0 <= amount <= 104
    
    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/coin-change
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
    
    自顶而下算法:

    题目要用最少数量的三枚硬币去凑11,因为有三种硬币,首先问题一定有最优解,所以可以转化为求分别凑10,9,6的子问题(subProblem), 10又可以分为凑9,8,5的子问题,以此类推。。。 经过穷举我们可以举出所有的情况,但如果如此暴力穷举,会造成效率低下,当硬币数量足够多,目标金额足够大,时间复杂度是指数级别的,这主要还是因为我们在不断的重复做一些之前已经做完的事情,所以我们要学会标记已经做过的东西,我们用memo数组来标记已经做好的事情,下一次遇到便能直接使用。代码如下:

    // An highlighted block
    class  SolutionTwo
    {
    	//此数组用于记录数据
    	int[] memo;
    	
    	public int coinChange(int [] coins, int amount){
    		memo = new int[amount+1];
    
    		Arrays.fill(memo,-666);
    		// 将数组 memo 中每个元素都初始化为-666
    	
    		return dp(coins,amount);
    	}
    	private int dp(int[] coins,int amount){
    		if(amount == 0)	return 0;
    		// oK
    		if(amount < 0) return -1;
    		// 此方法行不通
    		if(memo[amount] != -666) return memo[amount];
    		//判断是否已经算出memo[amount]
    		
    		int res = Integer.MAX_VALUE;
    		// 初始化结果
    		for(int coin:coins){
    			//计算子问题的结果
    			int subProblem = dp(coins, amount - coin); // 状态转移方程
    			//子问题无解则跳过
    			if(subProblem == -1) continue;
    			//在子问题中选择最优解,然后加一
    			res = Math.min(res,subProblem + 1); 
    		}
    		//把计算结果存入数组中
    		memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
    
    		return memo[amount];
    	}
    }
    

    部分递归过程如下:
    在这里插入图片描述
    强调文本

    加粗文本 通过一部分穷举我们已求出拼凑1-5每个数字的最佳拼凑方案,即已经得到memo[1] 到 memo[5] ,当再次拼6时便可以直接拿来用,故经过一部分递归我们可以得到memo[1] 到 memo[11] 之后的每一次拼凑只需拿到memo[i]的值,极大的减少了重复的动作,提高了效率。

    接下来我们再用自底而上去解决这个问题

    自底而上:

    dp[]数组的定义与上面类似,dp[i] = x 表示,当目标金额为i时,至少需要x枚硬币。依次算出dp【1】到dp【11】即可。

    代码如下:

    // An highlighted block
    import java.util.Arrays;
    
    class SolutionThree 
    {
    	public int coinChange(int[] coins, int amount){
    		int [] dp = new int[amount+1];
    		//dp数组全部初始化为特殊值amount + 1
    		Arrays.fill(dp,amount+1);
    		
    		//base case
    		dp[0] = 0;
    		//外层for循环在遍历所有状态的所有取值
    		for(int i=0; i<dp.length; i++){
    			//内层for循环在求所有选择的最小值
    			for(int coin:coins){
    				//子问题无解
    				if(i-coin < 0)	continue;
    				//状态转移
    				dp[i] = Math.min(dp[i],dp[i-coin]+1); // 状态转移方程
    			}
    		}
    		//判断能否凑出金额amount
    		return (dp[amount] == amount + 1) ? -1 : dp[amount];
    	}
    	public static void main(String[] args){
    
    		SolutionThree three = new SolutionThree();
    		int[] coins = {1,2,5};
    
    		System.out.println(three.coinChange(coins,11));
    	}
    }
    

    再用一道相似的例题去感受一下这种思想

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

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

    样例如下:

    // An highlighted block
    var foo = 'bar';
    示例 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 。
     
    
    提示:
    
    0 <= nums.length <= 100
    0 <= nums[i] <= 400
    通过次数264,868提交次数
    
    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/house-robber
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
    
    
    
    自顶向下代码:
    // An highlighted block
    class RubberOne 
    {
    	int[] memo;
        public int rob(int[] nums) {
            memo = new int[nums.length];
            Arrays.fill(memo,-1);
            return dp(nums,0);
        }
        private int dp(int[] nums, int start){
            if(start >= nums.length){
                return 0;
            }
            if(memo[start] != -1){
                return memo[start];
            }
            int res = Math.max(dp(nums,start+1), nums[start]+dp(nums,start+2));//状态转移方程
            
            memo[start] = res;
            return memo[start];
        }
    }
    
    
    自底而上代码:
    // An highlighted block
    class Solution {
        int rob(int[] nums){
            int n = nums.length;
    		//base case : dp[n] = 0
    		int[] dp = new int[n+2];//最大为dp[n+1]
    		Arrays.fill(dp,0);
    		for(int i=n-1; i>=0; i--){
    			dp[i] = Math.max(dp[i+1],nums[i]+dp[i+2]);//状态转移方程
    		}
    		return dp[0];
        }
    }
    

    1. 注脚的解释
      下面展示一些 内联代码片↩︎

    展开全文
  • 有时候使用动态规划的时候,先顶向下地思考当前问题,然后再用自底向上的方法实现。 通常情况下,记忆化搜索构建的算法程序一般都能满足时间复杂度、空间复杂度的需求,只不过使用动态规划的方案会使得整体代码...

    这里写目录标题

    在这里插入图片描述
    最优化原理指的最优策略具有这样的性质:不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简单来说就是一个最优策略的子策略也是必须是最优的,而所有子问题的局部最优解将导致整个问题的全局最优。如果一个问题能满足最优化原理,就称其具有最优子结构性质。

    这是判断问题能否使用动态规划解决的先决条件,如果一个问题不能满足最优化原理,那么这个问题就不适合用动态规划来求解。

    在这里插入图片描述
    整体来说,动态规划算法的时间复杂度比记忆化搜索好,因为没有递归调用函数的时间、以及系统的栈空间。

    一般来说,自上而下的解决问题比较容易想到,自下而上地思考比较难。

    有时候使用动态规划的时候,先自顶向下地思考当前问题,然后再用自底向上的方法实现。

    通常情况下,记忆化搜索构建的算法程序一般都能满足时间复杂度、空间复杂度的需求,只不过使用动态规划的方案会使得整体代码更加简洁,更加清晰。
    在这里插入图片描述

    一、斐波那契模型

    剑指 Offer 10- I. 斐波那契数列

    写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

    F(0) = 0,   F(1) = 1
    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
    

    斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

    答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

    示例 1:

    输入:n = 2
    输出:1
    

    示例 2:

    输入:n = 5
    输出:5
    

    提示:0 <= n <= 100


    在这里插入图片描述

    方法一:记忆化搜索(自上向下地解决问题)

    递归是自上向下地解决问题,我们 没有从最基本的问题开始解决,而是 假设已经解决了最基本的问题(子问题),即:假设我们已经求得了 f i b ( n − 1 ) fib(n - 1) fib(n1) 以及 f i b ( n − 2 ) fib(n - 2) fib(n2),求解 f i b ( n ) fib(n) fib(n)时,只需要将 f i b ( n − 1 ) fib(n - 1) fib(n1) 以及 f i b ( n − 2 ) fib(n - 2) fib(n2)相加即可。

    class Solution:
        def fib(self, n: int) -> int:
            memo = [-1] * (n + 1)
            def dfs(n):
                if n == 0:
                    return 0
                if n == 1:
                    return 1
    
                if memo[n] == -1:
                    memo[n] = dfs(n - 1) + dfs(n - 2)
    
                print("memo = ", memo)
    
                return memo[n]
    
            return dfs(n)%1000000007
    

    输入数据:

    10
    

    打印结果:

    memo =  [-1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, -1, -1, -1, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, -1, -1, -1, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 3, -1, -1, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 3, -1, -1, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 3, 5, -1, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 3, 5, -1, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 3, 5, 8, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 3, 5, 8, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 3, 5, 8, 13, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 3, 5, 8, 13, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 3, 5, 8, 13, 21, -1, -1]
    memo =  [-1, -1, 1, 2, 3, 5, 8, 13, 21, -1, -1]
    memo =  [-1, -1, 1, 2, 3, 5, 8, 13, 21, 34, -1]
    memo =  [-1, -1, 1, 2, 3, 5, 8, 13, 21, 34, -1]
    memo =  [-1, -1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
    

    输出结果:

    55
    

    方法二:动态规划(自下而上地解决问题)

    动态规划是自下而上地解决问题,我们从最基本的问题开始解决,先解决小数据量下问题的结果,然后层层递推,解决更大的数据量的问题的结果。

    class Solution:
        def fib(self, n: int) -> int:
            if n == 0:
                return 0
            dp = [-1] * (n + 1)
            dp[0] = 0
            dp[1] = 1
            for i in range(2, n + 1):
                dp[i] = dp[i - 1] + dp[i - 2]
            
            print("dp = ", dp)
            
            return dp[-1]%1000000007
    

    输入数据:

    10
    

    打印结果:

    dp =  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
    

    输出结果:

    55
    

    70. 爬楼梯

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

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

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

    示例 1:

    输入: 2
    输出: 2
    解释: 有两种方法可以爬到楼顶。
    1.  1 阶 + 1 阶
    2.  2 阶
    

    示例 2:

    输入: 3
    输出: 3
    解释: 有三种方法可以爬到楼顶。
    1.  1 阶 + 1 阶 + 1 阶
    2.  1 阶 + 2 阶
    3.  2 阶 + 1 阶
    

    在这里插入图片描述

    方法一:记忆化搜索(自上向下地解决问题)

    # 斐波那契数
    class Solution:
        def climbStairs(self, n: int) -> int:
            paths = [-1] * (n + 1)
            def dfs(n: int)-> int:
                # 递归结束条件
                if n == 0:
                    return 1
                if n == 1:
                    return 1
                
                # 递归
                if paths[n] == -1:
                    paths[n] = dfs(n - 1) + dfs(n - 2)
    
                return paths[n]
    
    
    
            return dfs(n)
    
    # 斐波那契数
    class Solution:
        def climbStairs(self, n: int) -> int:
            paths = {}
            def dfs(n: int)-> int:
                # 递归结束条件
                if n == 0:
                    return 1
                if n == 1:
                    return 1
                
                # 递归
                if paths.get(n) is None:
                    paths[n] = dfs(n - 1) + dfs(n - 2)
    
                return paths.get(n)
    
    
    
            return dfs(n)
    
    # 斐波那契数
    class Solution:
        def climbStairs(self, n: int) -> int:
            paths = {}
            def dfs(n: int)-> int:
                # 递归结束条件
                if n == 1:
                    return 1
                if n == 2:
                    return 2
                
                # 递归
                if paths.get(n) is None:
                    paths[n] = dfs(n - 1) + dfs(n - 2)
    
                return paths.get(n)
    
    
    
            return dfs(n)
    

    方法二:动态规划(自下而上地解决问题)

    # 斐波那契数
    class Solution:
        def climbStairs(self, n: int) -> int:
            # 构建一维动态数组
            dp = [-1] * (n + 1)
    
            # 初始化dp数组的边界
            dp[0] = 1
            dp[1] = 1
    
            for i in range(2, n + 1):
                dp[i] = dp[i - 1] + dp[i - 2]
    
            print("dp = ", dp)
            return dp[-1]
    

    输入数据:

    4
    

    打印结果:

    dp =  [1, 1, 2, 3, 5]
    

    输出结果:

    5
    

    剑指 Offer 10- II. 青蛙跳台阶问题【与“70. 爬楼梯”相同】

    二、路径问题

    62. 不同路径

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

    机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

    问总共有多少条不同的路径?

    示例 1:
    在这里插入图片描述

    输入:m = 3, n = 7
    输出:28
    

    示例 2:

    输入:m = 3, n = 2
    输出:3
    解释:
    从左上角开始,总共有 3 条路径可以到达右下角。
    1. 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右
    3. 向下 -> 向右 -> 向下
    

    示例 3:

    输入:m = 7, n = 3
    输出:28
    

    示例 4:

    输入:m = 3, n = 3
    输出:6
    

    提示:

    • 1 <= m, n <= 100
    • 题目数据保证答案小于等于 2 ∗ 1 0 9 2 * 10^9 2109

    在这里插入图片描述

    class Solution:
        def uniquePaths(self, m: int, n: int) -> int:
            # 构建dp数组
            dp = [[0 for _ in range(n)] for _ in range(m)]
    
            print("dp = ", dp)
    
            # 初始化dp数组的边界
            for j in range(n):
                dp[0][j] = 1
            for i in range(m):
                dp[i][0] = 1
    
            print("dp = ", dp)
    
            for i in range(1, m):
                for j in range(1, n):
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
            print("dp = ", dp)
    
            return dp[-1][-1]
    

    输入数据:

    3
    7
    

    打印:

    dp =  [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]
    dp =  [[1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0]]
    dp =  [[1, 1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6, 7], [1, 3, 6, 10, 15, 21, 28]]
    

    输出:

    28
    

    63. 不同路径 II

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

    现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
    在这里插入图片描述

    网格中的障碍物和空位置分别用 1 和 0 来表示。

    示例 1:
    在这里插入图片描述

    输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
    输出:2
    解释:
    3x3 网格的正中间有一个障碍物。
    从左上角到右下角一共有 2 条不同的路径:
    1. 向右 -> 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右 -> 向右
    

    示例 2:
    在这里插入图片描述

    输入:obstacleGrid = [[0,1],[0,0]]
    输出:1
    

    提示:

    • m == obstacleGrid.length
    • n == obstacleGrid[i].length
    • 1 <= m, n <= 100
    • obstacleGrid[i][j] 为 0 或 1

    在这里插入图片描述
    注意:初始化时,如果第一行或第一列有障碍物,则之后的初始化数据就为0
    在这里插入图片描述
    在递推的过程中,如果遇到障碍物,则将此处的路径数量置为0

    class Solution:
        def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
            if obstacleGrid[0][0] == 1:
                return 0
            m = len(obstacleGrid)
            n = len(obstacleGrid[0])
            # 构建dp数组
            dp = [[0 for _ in range(n)] for _ in range(m)]
    
            # 初始化dp边界
            for j in range(n):
                dp[0][j] = 1
                if obstacleGrid[0][j] == 1:
                    dp[0][j] = 0
                    break
            for i in range(m):
                dp[i][0] = 1
                if obstacleGrid[i][0] == 1:
                    dp[i][0] = 0
                    break
            
            print("dp = ", dp)
    
    
            for i in range(1, m):
                for j in range(1, n):
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                    if obstacleGrid[i][j] == 1:
                        dp[i][j] = 0
            
            print("dp = ", dp)
    
            return dp[-1][-1]
    

    输入:

    
    [[0,0],[1,1],[0,0]]
    

    打印:

    初始化:dp =  [[1, 1], [0, 0], [0, 0]]
    最终:dp =  [[1, 1], [0, 0], [0, 0]]
    

    输出:

    0
    

    64. 最小路径和

    给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

    说明:每次只能向下或者向右移动一步。

    示例 1:
    在这里插入图片描述

    输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
    输出:7
    解释:因为路径 1→3→1→1→1 的总和最小。
    

    示例 2:

    输入:grid = [[1,2,3],[4,5,6]]
    输出:12
    

    提示:

    • m == grid.length
    • n == grid[i].length
    • 1 <= m, n <= 200
    • 0 <= grid[i][j] <= 100

    方法一:直接递归(自顶向下) 超时

    思路:自顶向下的递归操作。
    a.边界条件:到递归到最后一个元素,或者超过边界时结束递归。
    b.递归式:因为只有向下和向右两种移动方式,得f(n,n) ==> min(f(n+1,n),min(n,n+1))

    大致的递归树如下:

    在这里插入图片描述
    从上图我们可以看到,递归的过程中有大量的重叠子问题,也就是重复递归。例如f(2,1)被重复调用了很多次,这也是时间复杂度较高的主要原因,在第二种方法中我们使用记忆化来优化这个问题。

    if not grid:
        return 0
    #数组的长和宽
    size_row,size_col = len(grid),len(grid[0])
    def helper(row,col):
        if row >= size_row or col >= size_col:
            return float("inf") #这里要定义一个较大的数,因为这个值会被返回到min函数中
        #到达最后一个元素的时候结束递归
        if row == size_row - 1 and col == size_col - 1:
            return grid[row][col]
        #自顶向下递归
        return grid[row][col] + min(helper(row+1,col),helper(row,col+1))
    
    return helper(0,0)
    

    方法二:记忆化搜索(自上向下地解决问题)

    思路:和方法1一样,也是基本的自顶向下的递归,唯一不同的是加入辅助数组nums在存储中间递归值。
    代码中有详细的注解,具体不再累述。

    class Solution:
        def minPathSum(self, grid: List[List[int]]) -> int:
            if not grid:
                return 0
            
            # 数组的长和宽
            rowSize ,colSize = len(grid) ,len(grid[0])
    
            # 定义记忆化需要的辅助数组
            memo = [[-1] *(colSize +1) for _ in range(rowSize +1)]
    
            def dfs(grid, row ,col):
                
    
                if row >= rowSize or col >= colSize:
                    return float("inf")  # 这里要定义一个较大的数,因为这个值会被返回到min函数中
                if row == rowSize - 1 and col == colSize - 1:
                    return grid[row][col]
    
                # 向下移动一步的情况
                if memo[row +1][col] != -1:
                    down = memo[row +1][col]
                else:
                    down = dfs(grid, row +1 ,col)
                    memo[row +1][col] = down
    
                # 向右移动的情况
                if memo[row][col +1] != -1:
                    right = memo[row][col +1]
                else:
                    right = dfs(grid, row ,col +1)
                    memo[row][col +1] = right
    
                return grid[row][col] + min(down ,right)
    
            return dfs(grid, 0 ,0)
    

    方法三:动态规划(自下而上地解决问题)

    相比较于记忆化,动态规划节省了调用递归栈的额外空间,所以在一定程度上,动规的空间复杂度是比记忆化的空间复杂度小的。而且通过运行,动规的运行时间要比记忆化的时间小很多。

    思路:这题的因为只有两种移动方式,故状态转移方程还是很容易看出的。

    确定状态:dp[i][j]表示从左上角到达grid[i][j]这个位置的最小路径和。

    状态转移方程:

    • 第一行的情况: d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] + g r i d [ i ] [ 0 ] dp[i][0] = dp[i-1][0]+grid[i][0] dp[i][0]=dp[i1][0]+grid[i][0]
    • 第一列的情况: d p [ 0 ] [ j ] = d p [ 0 ] [ j − 1 ] + g r i d [ 0 ] [ j ] dp[0][j] = dp[0][j-1] + grid[0][j] dp[0][j]=dp[0][j1]+grid[0][j]
    • 之外的情况: d p [ i ] [ j ] = g r i d [ i ] [ j ] + m i n ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] = grid[i][j] + min(dp[i-1][j],dp[i][j-1]) dp[i][j]=grid[i][j]+min(dp[i1][j],dp[i][j1])

    在这里插入图片描述

    class Solution:
        def minPathSum(self, grid: List[List[int]]) -> int:
            if not grid:
                return 0
    
            row = len(grid) #行
            col = len(grid[0])  #列
            dp = [[0]*col for _ in range(row)]  # 创建于grid二维数组相同形状的二维数组
    
            dp[0][0] = grid[0][0]   #初始化首位置
    
            #因为第一行和第一列属于特殊状态,需要先处理
            
            #处理边界状态:【初始化第一行元素】
            for i in range(1,row):
                dp[i][0] = dp[i-1][0]+grid[i][0]
    
            #处理边界状态:【初始化第一列元素】
            for j in range(1,col):
                dp[0][j] = dp[0][j-1] + grid[0][j]
    
            # 状态转移:【处理其他元素:遍历整个数组】
            for i in range(1,row):
                for j in range(1,col):
                    dp[i][j] = grid[i][j] + min(dp[i-1][j],dp[i][j-1]) #状态转移方程
            
            print("dp = ", dp)
    
            return dp[-1][-1]
    

    72. 编辑距离

    给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

    你可以对一个单词进行如下三种操作:

    • 插入一个字符
    • 删除一个字符
    • 替换一个字符

    示例 1:

    输入:word1 = "horse", word2 = "ros"
    输出:3
    解释:
    horse -> rorse (将 'h' 替换为 'r')
    rorse -> rose (删除 'r')
    rose -> ros (删除 'e')
    

    示例 2:

    输入:word1 = "intention", word2 = "execution"
    输出:5
    解释:
    intention -> inention (删除 't')
    inention -> enention (将 'i' 替换为 'e')
    enention -> exention (将 'n' 替换为 'x')
    exention -> exection (将 'n' 替换为 'c')
    exection -> execution (插入 'u')
    

    提示:

    • 0 <= word1.length, word2.length <= 500
    • word1 和 word2 由小写英文字母组成

    在这里插入图片描述

    class Solution:
        def minDistance(self, word1: str, word2: str) -> int:
            m = len(word1)
            n = len(word2)
            dp = [[float('inf') for _ in range(n + 1)] for _ in range(m + 1)]
            
            # 处理边界状态:【初始化第0行】
            for i in range(n + 1):
                dp[0][i] = i
            
            # 处理边界状态:【初始化第0列】
            for i in range(m + 1):
                dp[i][0] = i
    
            # 状态转移【i , j 代表 word1, word2 对应位置的 index】
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if word1[i - 1] == word2[j - 1]:    # 如果word1[:i][-1]==word2[:j][-1]
                        dp[i][j] = dp[i - 1][j - 1] 
                    else:   # 否则从三种状态中选一个最小的然后 +1
                        dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1
            
            return dp[-1][-1]
    

    120. 三角形最小路径和

    给定一个三角形 triangle ,找出自顶向下的最小路径和。

    每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。

    示例 1:

    输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
    输出:11
    解释:如下面简图所示:
       2
      3 4
     6 5 7
    4 1 8 3
    自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
    

    示例 2:

    输入:triangle = [[-10]]
    输出:-10
    

    提示:

    • 1 <= triangle.length <= 200
    • triangle[0].length == 1
    • triangle[i].length == triangle[i - 1].length + 1
    • − 1 0 4 < = t r i a n g l e [ i ] [ j ] < = 1 0 4 -10^4 <= triangle[i][j] <= 10^4 104<=triangle[i][j]<=104

    进阶:你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题吗?


    方法一:记忆化搜索(自上向下地解决问题)

    方法二:动态规划(自下而上地解决问题)

    根据动态规划的三大步骤来做题:

    • 第一步骤:定义数组元素的含义

      • 我们会用一个数组,来保存历史数组,假设用二维数组 dp[i][j] 吧。这个时候有一个非常非常重要的点,就是规定你这个数组元素的含义,在这个题目中,我们定义的就是dp[i][j]为题目给的最小路径。累加求和就可以了
    • 第二步骤:找出数组元素之间的关系式(即状态转移方程),这里就是有两种情况:

      • 第一列的元素来源路径只可能是由上一行对应列的元素移动而来
      • 在对角线上的元素只有可能是从上一个对角线元素移动过来
      • 其他位置的元素有以上两种方式移动过来(所以要求最小值)
    • 第三步骤:找出初始值。

      • 在一般题目中寻找初始值的时候,一定要注意不要找漏了。但是这个题目的初始值很好找,自顶向下,三角形,初始值就只可能是最顶上的元素
        Trick: 这个题目是累加的形式,所以也不需要定义全零数组,所以dp = triangle 元素也不需要初始化,真的方便
    class Solution:
        def minimumTotal(self, triangle: List[List[int]]) -> int:
            depth = len(triangle)
    
            # 构建dp
            dp = triangle
    
            #dp是一个list列表,同样也可以看成是一个二维数组,如图所示
            # [             [
            #     2,          [2],
            #     3,4        [3,4],
            #     6,5,7     [6,5,7],
            #     4,1,8,3  [4,1,8,3]
            # ]             ]
            # 可以知道3的下一行中相邻的结点为6和5,6的下一行中相邻的结点为4和1,5的下一行中相邻的结点为1和8
    
    
            # 初始化边界
            dp[0][0] = triangle[0][0]   # 对第一行的元素,不需要初始化。如:到2的最短路径就是2
            for i in range(1, depth):
                dp[i][0] = dp[i - 1][0] + triangle[i][0]    # 第一列的元素来源路径只可能是由上一行对应列的元素移动而来   
                dp[i][-1] = dp[i - 1][-1] + triangle[i][-1] # 最后一列的元素来源路径只可能是由上一行对应列的元素移动而来   
    
            print("初始化:dp = ", dp)
    
            # 状态转移
            for i in range(1, depth):
                for j in range(1, len(triangle[i]) - 1):
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j] # 移动方式只有向下和像45度方向移动两种情况,求两种移动路径的最小值
    
            print("最终:dp = ", dp)
    
            return min(dp[-1])
    
    class Solution:
        def minimumTotal(self, triangle: List[List[int]]) -> int:
            dp = triangle     #这边的初始化真的是牛逼,不仅不需要把把上面两行特殊的情况考虑进去,而且为下面也做了铺垫。因为是做累加,所以不需要初始化为0       
            m = len(dp) 
            #dp是一个list列表,同样也可以看成是一个二维数组,如图所示
            # [             [
            #     2,          [2],
            #     3,4        [3,4],
            #     6,5,7     [6,5,7],
            #     4,1,8,3  [4,1,8,3]
            # ]             ]
            # 可以知道3的下一行中相邻的结点为6和5,6的下一行中相邻的结点为4和1,5的下一行中相邻的结点为1和8
    
            for i in range(1, m): # 对第一行的元素,不需要初始化。如:到2的最短路径就是2
                for j in range(i+1):
                    #处理边界状态:【初始化第一列元素】:第一列的元素来源路径只可能是由上一行对应列的元素移动而来   
                    if j == 0:
                        dp[i][j] += dp[i-1][j]          
                    
                    #处理边界状态:【初始化最后一列元素】:最后一列的元素来源路径只可能是由上一行最后一列的元素移动而来【如:7的来源路径只有可能是从4来】
                    if j> 0 and j == i:
                        dp[i][j] += dp[i-1][j-1]
                    
                    # 状态转移:处理其他元素:对于不是第一列、最后一列的元素 【根据题目要求得到上面左边的图,移动方式只有向下和像45度方向移动两种情况】
                    elif (0 < j < i):
                        dp[i][j] += min(dp[i-1][j-1],dp[i-1][j]) #求两种移动路径的最小值
            
            print("dp = ", dp)
            
            return (min(dp[m-1]))
    

    打印结果:

    dp =  [[-1], [1, 2], [2, 0, -1]]
    

    三、数字问题

    343. 整数拆分

    给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

    示例 1:

    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1。
    

    示例 2:

    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
    

    说明: 你可以假设 n 不小于 2 且不大于 58。


    在这里插入图片描述
    在这里插入图片描述

    方法一:递归【超时 O ( 2 n ) O(2^n) O(2n)

    class Solution:
        def integerBreak(self, n: int) -> int:
            if n == 1:
                return 1
            result = -1
            for i in range(1, n):
                # i + (n - i)
                result = max(result, i * (n - i), i * self.integerBreak(n - i))
    
            return result
    

    方法二:记忆化搜索(自上向下地解决问题)【 O ( n 2 ) O(n^2) O(n2)

    class Solution:
        def integerBreak(self, n: int) -> int:
            
            memo = [-1] * (n + 1)
            
            def dfs(n):
                if n == 1:
                    return 1
    
                if memo[n] != -1:
                    return memo[n]
                
                result = 0
                
                for i in range(1, n):
                    result = max(result, i * (n - i), i * dfs(n - i))
                
                memo[n] = result
    
                print("memo = ", memo)
    
                return result
    
            return dfs(n)
    

    输入数据:

    10
    

    打印结果:

    memo =  [-1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, -1, -1, -1, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 4, -1, -1, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 4, 6, -1, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 4, 6, 9, -1, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 4, 6, 9, 12, -1, -1, -1]
    memo =  [-1, -1, 1, 2, 4, 6, 9, 12, 18, -1, -1]
    memo =  [-1, -1, 1, 2, 4, 6, 9, 12, 18, 27, -1]
    memo =  [-1, -1, 1, 2, 4, 6, 9, 12, 18, 27, 36]
    

    方法三:动态规划(自下而上地解决问题)【 O ( n 2 ) O(n^2) O(n2)

    class Solution:
        def integerBreak(self, n: int) -> int:
            # 构建dp【dp[i] 表示将数字i分割(至少分割成两部分)后得到的最大乘积】
            dp = [-1] * (n + 1)
    
            # 初始化dp
            dp[1] = 1
    
            # 状态转移
            for i in range(2, n + 1):
                for j in range(1, i):
                    dp[i] = max(dp[i], j * (i - j), j * dp[i - j])  # j * (i - j) 表示将i分割成2部分j与(i-j),j * dp[i - j]表示将(i-j)继续分割
    
            print("dp = ", dp)
    
            return dp[n]
    
    class Solution:
        def integerBreak(self, n: int) -> int:
            if n == 1:
                return 1
            # dp[i] 表示将数字i分割(至少分割成两部分)后得到的最大乘积
            dp = [-1] * (n + 1)
            dp[1] = 1
            # 层层递推,求解dp[i]
            for i in range(2, n + 1):
                # i = j + (i - j)
                for j in range(1, i):
                    # j * (i - j) 表示将i分割成2部分j与(i-j),j * dp[i - j]表示将(i-j)继续分割
                    dp[i] = max(dp[i], j * (i - j), j * dp[i - j])  
            print("dp = ", dp)
            return dp[n]
    

    输入数据:

    10
    

    打印结果:

    dp =  [-1, 1, 1, 2, 4, 6, 9, 12, 18, 27, 36]
    

    91. 解码方法

    一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

    'A' -> 1
    'B' -> 2
    ...
    'Z' -> 26
    

    要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:

    • “AAJF” ,将消息分组为 (1 1 10 6)
    • “KJF” ,将消息分组为 (11 10 6)

    注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。

    给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。

    题目数据保证答案肯定是一个 32 位 的整数。

    示例 1:

    输入:s = "12"
    输出:2
    解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
    

    示例 2:

    输入:s = "226"
    输出:3
    解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
    

    示例 3:

    输入:s = "0"
    输出:0
    解释:没有字符映射到以 0 开头的数字。
    含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
    由于没有字符,因此没有有效的方法对此进行解码,因为所有数字都需要映射。
    

    示例 4:

    输入:s = "06"
    输出:0
    解释:"06" 不能映射到 "F" ,因为字符串含有前导 0("6" 和 "06" 在映射中并不等价)。
    

    提示:

    1 <= s.length <= 100
    s 只包含数字,并且可能包含前导零。


    在这里插入图片描述
    在这里插入图片描述

    class Solution:
        def numDecodings(self, s: str) -> int:
            n = len(s)
            
            # 构建dp【dp[i]代表字符串的[0: i]左闭右闭范围的字符的解码方式数量】
            dp = [0] * (n + 1)
    
            # 初始化dp
            dp[0] = 1 
            
            s = '0' + s
    
            # 状态转移【i表示字符串中第i个字符】
            for i in range(1, n + 1):
    
                if 1 <= int(s[i]) <= 9:
                    dp[i] = dp[i - 1]
                    
                if 10 <= int(s[i - 1]) * 10 + int(s[i]) <= 26:
                    dp[i] += dp[i - 2]
                   
            return dp[-1]
    
    class Solution:
        def numDecodings(self, s: str) -> int:
            n = len(s)
            
            # 构建dp【dp[i]代表字符串的[0: i]左闭右闭范围的字符的解码方式数量】
            dp = [0] * (n + 1)
    
            # 初始化dp
            dp[0] = 1 
            
            s = '0' + s
    
            # 状态转移【i表示字符串中第i个字符】
            for i in range(1, n + 1):
    
                if 1 <= int(s[i]) <= 9:
                    dp[i] += dp[i - 1]
                    
                if 10 <= int(s[i - 1]) * 10 + int(s[i]) <= 26:
                    dp[i] += dp[i - 2]
                   
            return dp[-1]
    

    四、打家劫舍问题

    198. 打家劫舍

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

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

    示例 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.length <= 100
    • 0 <= nums[i] <= 400

    在这里插入图片描述
    在这里插入图片描述

    方法一:递归【超时 O ( 2 n ) O(2^n) O(2n)

    class Solution:
        def rob(self, nums: List[int]) -> int:
            def tryRob(nums, index):
                if index >= len(nums):
                    return 0
                result = 0
                for i in range(index, len(nums)):
                    result = max(result, nums[i] + tryRob(nums, i + 2))
                
                return result
    
            return tryRob(nums, 0)
    

    方法二:记忆化搜索(自上向下地解决问题)【 O ( n 2 ) O(n^2) O(n2)

    class Solution:
        def rob(self, nums: List[int]) -> int:
            memo = [-1] * len(nums)
            def dfs(nums, index):
                if index >= len(nums):
                    return 0
                
                if memo[index] != -1:
                    return memo[index]
                
                result = 0
                for i in range(index, len(nums)):
                    result = max(result, nums[i] + dfs(nums, i + 2))
                
                memo[index] = result    
    
                print("memo = ", memo) 
                
                return result
    
            return dfs(nums, 0)
    

    输入数据:

    [2,7,9,3,1]
    

    打印结果:

    memo =  [-1, -1, -1, -1, 1]
    memo =  [-1, -1, 10, -1, 1]
    memo =  [-1, -1, 10, 3, 1]
    memo =  [12, -1, 10, 3, 1]
    

    输出结果:

    12
    

    方法三:动态规划(自下而上地解决问题)

    在这里插入图片描述

    class Solution:
        def rob(self, nums: List[int]) -> int:
            if not nums:
                return 0
    
            length = len(nums)
            if length == 1:
                return nums[0]
            
            # 构建dp数组
            dp = [0] * length
    
            # 初始化dp数组
            dp[0] = nums[0]
            dp[1] = max(nums[0], nums[1])
    
            # 构建状态转移方程
            for i in range(2, length):
                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
            
            print("dp = ", dp)
    
            return dp[-1]
    

    输入数据:

    [2,7,9,3,1]
    

    打印结果:

    dp =  [2, 7, 11, 11, 12]
    

    输出结果:

    12
    

    方法四:动态规划(自下而上地解决问题)【 O ( n 2 ) O(n^2) O(n2)

    动态规划,不同的初始状态

    class Solution:
        def rob(self, nums: List[int]) -> int:
            length = len(nums)
            if length == 0:
                return 0
            
            dp = [-1] * length
            # 初始化最后一家
            dp[length - 1] = nums[length - 1]
    		
    		# 构建状态转移方程
            for i in range(length - 2, -1, -1):
                for j in range(i, length):
                    dp[i] = max(dp[i], nums[j] + (dp[j + 2] if j +2 < length else 0))
            
            print("dp = ", dp)
            
            return dp[0]
    

    输入数据:

    [2,7,9,3,1]
    

    打印结果:

    dp =  [12, 10, 10, 3, 1]
    

    输出结果:

    12
    

    213. 打家劫舍 II

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

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

    示例 1:

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

    示例 2:

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

    示例 3:

    输入:nums = [0]
    输出:0
    

    提示:

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

    class Solution:
        def rob(self, nums: List[int]) -> int:
            n = len(nums)
            if n == 0:
                return 0
            if n == 1:
                return nums[0]
            
            # 线性打家劫舍
            def rob_link(sub_nums: List[int]) ->int:
                m = len(sub_nums)
                if m == 0:
                    return 0
                if m == 1:
                    return sub_nums[0]
                
                dp = [0] * m
                dp[0] = sub_nums[0]
                dp[1] = max(sub_nums[0], sub_nums[1])
    
                for i in range(2, m):
                    dp[i] = max(dp[i - 2] + sub_nums[i], dp[i - 1])
                
                return dp[-1]
    
            # 因为第一个房屋和最后一个房屋是紧挨着的,所以我们把该问题拆分成两个线性打家劫舍问题
            # 从左到右不包括最后值的数组nums[0: n- 1]、从左到右不包括第一个值的数组nums[1: n],取其最大值
            result = max(rob_link(nums[0: n- 1]), rob_link(nums[1: n])) 
    
            return result
    

    337. 打家劫舍 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.
    

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def rob(self, root: TreeNode) -> int:
    
            # 参数为node节点, dfs方法输出一个二维数组:node节点的[偷值, 不偷值]
            def dfs(node):
                
                # 递归终止条件
                if not node: 
                    return 0, 0  # 偷,不偷
                
                # 递归
                left = dfs(node.left)   # left是一个tuple, 为 node 左侧子节点的 (偷值, 不偷值)
                right = dfs(node.right)   # right是一个tuple, 为 node 右侧子节点的 (偷值, 不偷值)
    
                # 主体逻辑部分
                v1 = node.val + left[1] + right[1]  # 偷当前节点, 则左右子节点都不能偷
                v2 = max(left) + max(right) # 不偷当前节点, 则取左右子树中最大的值进行相加得到当前节点的最终结果
    
                return v1, v2
    
            return max(dfs(root))
    

    五、股票问题

    我们并不是要考虑买还是卖,而是要最大化手里持有的钱。

    买股票手里的钱减少,卖股票手里的钱增加,无论什么时刻,我们要保证手里的钱最多。

    我们这一次买还是卖只跟上一次我们卖还是买的状态有关。

    121、122 这两个问题唯一的不同点在于我们是买一次还是买无穷多次,而代码就只有 0-p 和 sell-p 的区别。因为如果买无穷多次,就需要上一次卖完的状态。如果只买一次,那么上一个状态一定是0。

    121. 买卖股票的最佳时机

    给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

    你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

    返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

    示例 1:

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

    示例 2:

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

    提示:

    • 1 < = p r i c e s . l e n g t h < = 1 0 5 1 <= prices.length <= 10^5 1<=prices.length<=105
    • 0 < = p r i c e s [ i ] < = 1 0 4 0 <= prices[i] <= 10^4 0<=prices[i]<=104

    方法一:暴力法【 O ( n 2 ) O(n^2) O(n2)

    思路:枚举所有发生一次交易的股价差。

    from typing import List
    
    
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            result = 0
            days = len(prices)
            for i in range(days):
                for j in range(i):
                    result = max(result, prices[i] - prices[j])
    
            return result
    
    
    solution = Solution()
    prices = [7, 1, 5, 3, 6, 4]
    result = solution.maxProfit(prices)
    print("result = ", result)
    

    方法二:一次遍历

    股票问题的方法就是 动态规划,因为它包含了重叠子问题,即买卖股票的最佳时机是由之前买或不买的状态决定的,而之前买或不买又由更早的状态决定的…

    由于本题只有一笔交易(买入卖出),因此除了动态规划,我们还可以使用更加简便的方法实现。

    https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/5xing-jie-jue-suo-you-gu-piao-mai-mai-we-evro/

    from typing import List
    
    # 其中buy和sell都代表操作之后手里的钱
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            buy = -float("inf")  # 当天买股票,手里持有的现金数
            sell = 0  # 当天卖股票,手里持有的现金数
    
            for price in prices:
                buy = max(buy, 0 - price)  # 当天买该支股票后,手里持有的现金数
                sell = max(sell, buy + price)  # 当天卖该支股票后,手里持有的现金数
    
            return sell
    
    
    solution = Solution()
    prices = [7, 1, 5, 3, 6, 4]
    result = solution.maxProfit(prices)
    print("result = ", result)
    
    from typing import List
    
    
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            minprice = float('inf')  # 当天买股票,最小成本
            maxprofit = 0  # 当天卖股票,最大利润
    
            for price in prices:
                minprice = min(minprice, price)  # 买该支股票最小成本
                maxprofit = max(maxprofit, price - minprice)  # 卖该支股票后的最大利润
    
            return maxprofit
    
    
    solution = Solution()
    prices = [7, 1, 5, 3, 6, 4]
    result = solution.maxProfit(prices)
    print("result = ", result)
    

    方法三:动态规划

    在这里插入图片描述

    from typing import List
    
    
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            n = len(prices)
            if n == 0:
                return 0
    
            # 构建dp数组
            dp = [0] * n
    
            minprice = prices[0]
    
            # 状态转移
            for i in range(1, n):
                minprice = min(minprice, prices[i])
                dp[i] = max(dp[i - 1], prices[i] - minprice)
    
            print("dp = ", dp)
    
            return dp[-1]
    
    
    solution = Solution()
    prices = [7, 1, 5, 3, 6, 4]
    result = solution.maxProfit(prices)
    print("result = ", result)
    

    打印结果:

    dp =  [0, 0, 4, 4, 5, 5]
    result =  5
    

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

    给定一个数组 prices ,其中 prices[i] 是一支给定股票第 i 天的价格。

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

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

    示例 1:

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

    示例 2:

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

    示例 3:

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

    提示:

    • 1 < = p r i c e s . l e n g t h < = 3 ∗ 1 0 4 1 <= prices.length <= 3 * 10^4 1<=prices.length<=3104
    • 0 < = p r i c e s [ i ] < = 1 0 4 0 <= prices[i] <= 10^4 0<=prices[i]<=104

    方法一:贪心算法

    在这里插入图片描述

    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            result = 0 
            for i in range(1, len(prices)):
                profit = prices[i] - prices[i - 1]  # 当天的利润
                if profit >= 0:
                    result += profit
            return result
    
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            size = len(prices)
    
            ans = 0
            for i in range(1, size):
                # 这里仅在存在利润的情况进行计算累加利润
                # 也就是前后两天股票价格差大于 0 的情况
                ans += max(0, prices[i]-prices[i-1])
            
            return ans
    

    方法二:一次遍历

    from typing import List
    
    # 其中buy和sell都代表操作之后手里的钱
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            buy = -float("inf")  # 当天买股票,手里持有的现金数
            sell = 0  # 当天卖股票,手里持有的现金数
    
            for price in prices:
                buy = max(buy, sell - price)  # 当天买该支股票后,手里持有的现金数
                sell = max(sell, buy + price)  # 当天卖该支股票后,手里持有的现金数
    
            return sell
    
    
    solution = Solution()
    prices = [7, 1, 5, 3, 6, 4]
    result = solution.maxProfit(prices)
    print("result = ", result)
    

    方法三:动态规划

    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
    
            n = len(prices)
    
            if not prices:
                return 0
    
            dp = [[0, 0] for _ in range(n+1)]
    
            dp[0][1] = float('-inf')
    
            for i in range(1, n+1):
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])
                dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1])
            
            print("dp = ", dp)
            
            return dp[-1][0]
    

    输入数据:

    [7,1,5,3,6,4]
    

    打印:

    dp =  [[0, -inf], [0, -7], [0, -1], [4, -1], [4, 1], [7, 1], [7, 3]]
    

    输出结果:

    7
    

    优化:状态压缩,每天的最大利润至于前一天的利润有关

    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            # 优化,状态压缩,每天的最大利润至于前一天的利润有关
            if not prices:
                return 0
            
            dp_0 = 0                # 手里没股票
            dp_1 = float('-inf')    # 手里有股票
    
            for i in range(len(prices)):
                dp_0 = max(dp_0, dp_1 + prices[i])
                dp_1 = max(dp_1, dp_0 - prices[i])
    
            return dp_0
    

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

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

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

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

    示例:

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

    方法一:一次遍历

    这道题只是“122. 买卖股票的最佳时机 II”的变形,卖完要隔一天才能买,那么就多记录上一次卖的状态即可。

    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
    
            buy = -float("inf")
            sell_pre = 0
            sell = 0
    
            for p in prices:
                buy = max(buy, sell_pre - p)
                sell_pre, sell = sell, max(sell, buy + p)
                     
            return sell
    

    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.

    方法一:一次遍历

    这道题只是“122. 买卖股票的最佳时机 II”的变形,每次买卖需要手续费,那么我们买的时候减掉手续费就行了。

    class Solution:
        def maxProfit(self, prices: List[int], fee: int) -> int:
    
            buy = -float("inf")  # 当天买股票,手里持有的现金数
            sell = 0  # 当天卖股票,手里持有的现金数
    
            for price in prices:
                buy = max(buy, sell - price - fee)  # 当天买该支股票后,手里持有的现金数
                sell = max(sell, buy + price)  # 当天卖该支股票后,手里持有的现金数
    
            return sell
    

    123. 买卖股票的最佳时机 III【困难】

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

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

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

    示例 1:

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

    示例 2:

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

    示例 3:

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

    示例 4:

    输入:prices = [1]
    输出:0
    

    提示:

    • 1 < = p r i c e s . l e n g t h < = 1 0 5 1 <= prices.length <= 10^5 1<=prices.length<=105
    • 0 < = p r i c e s [ i ] < = 1 0 5 0 <= prices[i] <= 10^5 0<=prices[i]<=105

    方法一:一次遍历

    只允许最多买两次,那么就有四个状态,第一次买,第一次卖,第二次买,第二次卖。还是那句话,无论什么状态,我们要保证手里的钱最多。

    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            
            # 能买卖两次,故定义两对对buy和sell
            buy_1 = -float("inf")
            buy_2 = -float("inf")
            sell_1 = 0
            sell_2 = 0
    
            for price in prices:
    
                # 第一次进行买和卖:买时花钱,卖时挣钱
                buy_1 = max(buy_1, 0 - price)
                sell_1 = max(sell_1, buy_1 + price)
    
                # 第二次进行买和卖:买时花钱,卖时挣钱
                buy_2 = max(buy_2, sell_1 - price)
                sell_2 = max(sell_2, buy_2 + price)
                
            return sell_2
    

    188. 买卖股票的最佳时机 IV【困难】

    给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

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

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

    示例 1:

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

    示例 2:

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

    提示:

    • 0 <= k <= 100
    • 0 <= prices.length <= 1000
    • 0 <= prices[i] <= 1000

    方法一:一次遍历

    “123. 买卖股票的最佳时机 3”最多两次我们有2x2个状态,那么k次我们就需要kx2个状态。

    那么我们并不需要像“123. 买卖股票的最佳时机 3”那样真的列kx2个参数,我们只需要两个数组就可以了。

    class Solution:
        def maxProfit(self, k: int, prices: List[int]) -> int:
            n = len(prices)
            k = min(k, n // 2)
    
            buy = [-float("inf")] * (k+1)
            sell = [0] * (k+1)
    
            for price in prices:
                for i in range(1, k+1):
                    # 第i次进行买和卖:买时花钱,卖时挣钱
                    buy[i] = max(buy[i], sell[i-1] - price)
                    sell[i] = max(sell[i], buy[i] + price)
    
            return sell[-1]
    

    六、背包问题

    在这里插入图片描述

    背包问题具备的特征:

    是否可以根据一个 target(直接给出或间接求出),target 可以是数字也可以是字符串,再给定一个数组 arrs,问:能否使用 arrs 中的元素做各种排列组合得到 target。

    背包问题解法:

    • 01 背包问题:
      1. 如果是 01 背包,即数组中的元素不可重复使用,外循环遍历 arrs,内循环遍历 target,且内循环倒序:
      2. 0-1背包问题的状态转移方程:
        dp[i][j] = max(dp[i - 1][j], values[i] + dp[i - 1][j - weights[i]])
        
    • 完全背包问题:
      1. 如果是完全背包,即数组中的元素可重复使用并且不考虑元素之间顺序,arrs 放在外循环(保证 arrs 按顺序),target在内循环。且内循环正序。
      2. 如果组合问题需考虑元素之间的顺序,需将 target 放在外循环,将 arrs 放在内循环,且内循环正序。
      3. 完全背包问题的状态转移方程:
        dp[i][j] = 
        

    0-1背包问题

    n n n 件物品和一个容量为 C C C 的背包,第 i i i 件物品消耗的容量为 C i C_i Ci,价值为 v i v_i vi,求解放入哪些物品可以使得背包中总价值最大。例如:有3个物品,物品的重量分别是[1, 2, 3],价值分别为 [6, 10, 12],背包可容纳的总重量为5。计算该背包可容纳物品的最大价值。


    在这里插入图片描述

    方法一:记忆化搜索(自上向下地解决问题)

    from typing import List
    
    
    class Solution:
        def KnapSack01(self, weights: List[int], values: List[int], Capacity: int) -> int:
            length = len(weights)
            memo = [[-1] * (Capacity + 1) for _ in range(length)]
    
            # 用 [0, 1, ..., index] 的物品, 填充容积为 capacity 的背包的最大价值
            def bestValue(weights, values, index, capacity):
                if index < 0 or capacity <= 0:
                    return 0
    
                if memo[index][capacity] != -1:
                    return memo[index][capacity]
    
                result = bestValue(weights, values, index - 1, capacity)
                
                if capacity >= weights[index]:
                    result = max(result, values[index] + bestValue(weights, values, index - 1, capacity - weights[index]))
    
                memo[index][capacity] = result
    
                return result
    
            return bestValue(weights, values, length - 1, Capacity)
    
    
    solution = Solution()
    weights = [1, 2, 3]
    values = [6, 10, 12]
    Capacity = 5
    result = solution.KnapSack01(weights, values, Capacity)
    print("result = ", result)
    

    输出结果:

    result =  22
    

    方法二:动态规划(自下而上地解决问题)【 O ( n ∗ C ) O(n*C) O(nC)

    在这里插入图片描述

    from typing import List
    
    
    class Solution:
        def KnapSack01(self, weights: List[int], values: List[int], Capacity: int) -> int:
            size = len(weights)
            if size == 0:
                return 0
    
            # dp[i][j]:表示考虑 0~i的物品,容积为 j 的背包的最大价值
            dp = [[-1] * (Capacity + 1) for _ in range(size)]
    
            # 初始化第一行
            for j in range(Capacity + 1):
                dp[0][j] = values[0] if j >= weights[0] else 0
    
            # 遍历每一个物品
            for i in range(1, size):
                # 当背包的容量逐渐增加时,考虑是否放入当前物品
                for j in range(1, Capacity + 1):
                    # 如果不放入物品i,则当前背包的总价值和放入上一个物品后的背包总价值一样
                    valueWithout_i = dp[i - 1][j]
                    # 如果放入物品i(前提是放得下这件物品),则放入物品i后的背包剩余空间 (j - weights[i]) 可存放的物品价值为:dp[i - 1][j - weights[i]]
                    valueWith_i = values[i] + dp[i - 1][j - weights[i]] if j >= weights[i] else 0
                    # 取较大值
                    dp[i][j] = max(valueWithout_i, valueWith_i)
    
            return dp[-1][-1]
    
    
    solution = Solution()
    weights = [2, 1, 3]
    values = [10, 6, 12]
    Capacity = 5
    result = solution.KnapSack01(weights, values, Capacity)
    print("result = ", result)
    
    from typing import List
    
    
    class Solution:
        def KnapSack01(self, weights: List[int], values: List[int], Capacity: int) -> int:
            size = len(weights)
            if size == 0:
                return 0
    
            # dp[i][j]:表示考虑 0~i的物品,容积为 j 的背包的最大价值
            dp = [[-1] * (Capacity + 1) for _ in range(size)]
    
            # 初始化第一行
            for j in range(Capacity + 1):
                dp[0][j] = values[0] if j >= weights[0] else 0
    
            for i in range(1, size):  # 遍历每一个物品
                for j in range(1, Capacity + 1):
                    # 如果不放入物品i,则当前背包的总价值和放入上一个物品后的背包总价值一样;如果放入物品i(前提是放得下这件物品),则放入物品i后的背包剩余空间 (j - weights[i]) 可存放的物品价值为:dp[i - 1][j - weights[i]]
                    dp[i][j] = max(dp[i - 1][j], values[i] + dp[i - 1][j - weights[i]] if j >= weights[i] else 0)  # “不放入物品 i” 与 “放入物品 i” 的较大值
    
            return dp[-1][-1]
    
    
    solution = Solution()
    weights = [2, 1, 3]
    values = [10, 6, 12]
    Capacity = 5
    result = solution.KnapSack01(weights, values, Capacity)
    print("result = ", result)
    

    输出结果:

    result =  22
    

    方法三:动态规划+空间优化(使用2行数组)(自下而上地解决问题)【 O ( 2 ∗ C ) O(2*C) O(2C)

    观察上面的代码,会发现,当更新 d p [ i ] [ . . ] dp[i][..] dp[i][..] 时,只与 d p [ i − 1 ] [ . . ] dp[i-1][..] dp[i1][..] 有关,也就是说,我们没有必要使用 O ( n ∗ C ) O(n*C) O(nC) 的空间,而是只使用 O ( C ) O(C) O(C) 的空间即可。理论上,只需要保持2行元素。

    在这里插入图片描述

    from typing import List
    
    
    class Solution:
        def KnapSack01(self, weights: List[int], values: List[int], Capacity: int) -> int:
            size = len(weights)
            if size == 0:
                return 0
    
            # dp[i][j]:表示考虑 0~i的物品,容积为 j 的背包的最大价值,使用 2行即可
            dp = [[-1] * (Capacity + 1) for _ in range(2)]
    
            # 初始化第一行
            for j in range(Capacity + 1):
                dp[0][j] = values[0] if j >= weights[0] else 0
    
            for i in range(1, size):
                for j in range(1, Capacity + 1):
                    dp[i % 2][j] = max(dp[(i - 1) % 2][j], values[i] + dp[(i - 1) % 2][j - weights[i]] if j >= weights[i] else 0)  # “不放入物品 i” 与 “放入物品 i” 的较大值
    
            return dp[(size - 1) % 2][Capacity]
    
    
    solution = Solution()
    weights = [1, 2, 3]
    values = [6, 10, 12]
    Capacity = 5
    result = solution.KnapSack01(weights, values, Capacity)
    print("result = ", result)
    

    方法四:动态规划+空间优化(使用1行数组)(自下而上地解决问题)【 O ( C ) O(C) O(C)

    from typing import List
    
    
    class Solution:
        def KnapSack01(self, weights: List[int], values: List[int], Capacity: int) -> int:
            size = len(weights)
            if size == 0:
                return 0
    
            # dp[j]:表示容积为 j 的背包的最大价值
            dp = [-1] * (Capacity + 1)
    
            # 初始化一维数组
            for j in range(Capacity + 1):
                dp[j] = values[0] if j >= weights[0] else 0
    
            for i in range(1, size):
                for j in range(Capacity, weights[i] - 1, -1):
                    dp[j] = max(dp[j], values[i] + dp[j - weights[i]])  # “不放入物品 i” 与 “放入物品 i” 的较大值
    
            return dp[-1]
    
    
    solution = Solution()
    weights = [1, 2, 3]
    values = [6, 10, 12]
    Capacity = 5
    result = solution.KnapSack01(weights, values, Capacity)
    print("result = ", result)
    

    416. 分割等和子集【01 背包问题】【中等】

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

    示例 1:

    输入:nums = [1,5,11,5]
    输出:true
    解释:数组可以分割成 [1, 5, 5] 和 [11] 。
    

    示例 2:

    输入:nums = [1,2,3,5]
    输出:false
    解释:数组不能分割成两个元素和相等的子集。
    

    提示:

    • 1 <= nums.length <= 200
    • 1 <= nums[i] <= 100

    在这里插入图片描述

    class Solution:
        def canPartition(self, nums: List[int]) -> bool:
            # 若能分成元素和相等的两个子集,则必然和能被二整除
            total = sum(nums)
            if total % 2 or len(nums) == 1: 
                return False
            
            target = total // 2
            
            # 构建dp数组用于存储子集的和从0到target是否可能取到的情况【dp[i]]含义:有没有和为i的子集,有为True,没有为False】
            dp = [False] * (target + 1)
    
            # 初始化dp边界
            dp[0] = True
    
            for num in nums:
                for i in range(target, num-1, -1):
                    dp[i] = dp[i] | dp[i-num]
            
            print("dp = ", dp)
            return dp[-1]
    

    输入数据:

    [1,5,11,5]
    

    打印:

    dp =  [True, True, False, False, False, True, True, False, False, False, True, True]
    

    输出结果:

    true
    

    494. 目标和【01 背包问题】【中等】

    给你一个整数数组 nums 和一个整数 target 。

    向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式 :

    • 例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 “+2-1” 。
      返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

    示例 1:

    输入:nums = [1,1,1,1,1], target = 3
    输出:5
    解释:一共有 5 种方法让最终目标和为 3 。
    -1 + 1 + 1 + 1 + 1 = 3
    +1 - 1 + 1 + 1 + 1 = 3
    +1 + 1 - 1 + 1 + 1 = 3
    +1 + 1 + 1 - 1 + 1 = 3
    +1 + 1 + 1 + 1 - 1 = 3
    

    示例 2:

    输入:nums = [1], target = 1
    输出:1
    

    提示:

    • 1 <= nums.length <= 20
    • 0 <= nums[i] <= 1000
    • 0 <= sum(nums[i]) <= 1000
    • -1000 <= target <= 100

    在这里插入图片描述

    完全背包问题

    n n n 种物品和一个容量为 C C C 的背包,每种物品都有无限件可用,第 i i i 件物品消耗的容量为 C i C_i Ci,价值为 v i vi vi,求解放入哪些物品可以使得背包中总价值最大。


    完全背包问题的状态转移方程:

    
    

    139. 单词拆分【完全背包问题】【中等】

    给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

    说明:

    • 拆分时可以重复使用字典中的单词。
    • 你可以假设字典中没有重复的单词。

    示例 1:

    输入: s = "leetcode", wordDict = ["leet", "code"]
    输出: true
    解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
    

    示例 2:

    输入: s = "applepenapple", wordDict = ["apple", "pen"]
    输出: true
    解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
         注意你可以重复使用字典中的单词。
    

    示例 3:

    输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
    输出: false
    

    在这里插入图片描述

    279. 完全平方数【完全背包问题】【中等】

    给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

    给你一个整数 n ,返回和为 n 的完全平方数的 最少数量 。

    完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

    示例 1:

    输入:n = 12
    输出:3 
    解释:12 = 4 + 4 + 4
    

    示例 2:

    输入:n = 13
    输出:2
    解释:13 = 4 + 9
    

    提示: 1 < = n < = 1 0 4 1 <= n <= 10^4 1<=n<=104


    在这里插入图片描述

    377. 组合总和 Ⅳ【考虑排列顺序的完全背包问题】【中等】

    给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

    题目数据保证答案符合 32 位整数范围。

    示例 1:

    输入:nums = [1,2,3], target = 4
    输出:7
    解释:
    所有可能的组合为:
    (1, 1, 1, 1)
    (1, 1, 2)
    (1, 2, 1)
    (1, 3)
    (2, 1, 1)
    (2, 2)
    (3, 1)
    请注意,顺序不同的序列被视作不同的组合。
    

    示例 2:

    输入:nums = [9], target = 3
    输出:0
    

    提示:

    • 1 <= nums.length <= 200
    • 1 <= nums[i] <= 1000
    • nums 中的所有元素 互不相同
    • 1 <= target <= 1000

    进阶:如果给定的数组中含有负数会发生什么?问题会产生何种变化?如果允许负数出现,需要向题目中添加哪些限制条件?


    在这里插入图片描述

    322. 零钱兑换【不考虑排列顺序的完全背包问题】【中等】

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

    你可以认为每种硬币的数量是无限的。

    示例 1:

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

    示例 2:

    输入:coins = [2], amount = 3
    输出:-1
    

    示例 3:

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

    示例 4:

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

    示例 5:

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

    提示:

    • 1 <= coins.length <= 12
    • 1 < = c o i n s [ i ] < = 2 31 − 1 1 <= coins[i] <= 2^{31} - 1 1<=coins[i]<=2311
    • 0 < = a m o u n t < = 1 0 4 0 <= amount <= 10^4 0<=amount<=104

    在这里插入图片描述

    518. 零钱兑换 II【不考虑排列顺序的完全背包问题】【中等】

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

    示例 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 位符号整数

    在这里插入图片描述

    474. 一和零【中等】

    给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

    请你找出并返回 strs 的最大子集的大小,该子集中 最多 有 m 个 0 和 n 个 1 。

    如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。

    示例 1:

    输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
    输出:4
    解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。
    其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。
    

    示例 2:

    输入:strs = ["10", "0", "1"], m = 1, n = 1
    输出:2
    解释:最大的子集是 {"0", "1"} ,所以答案是 2 。
    

    提示:

    • 1 <= strs.length <= 600
    • 1 <= strs[i].length <= 100
    • strs[i] 仅由 ‘0’ 和 ‘1’ 组成
    • 1 <= m, n <= 100

    七、最长上升子序列问题(Longest Increasing Sequence)

    300. 最长递增子序列

    给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

    子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

    示例 1:

    输入:nums = [10,9,2,5,3,7,101,18]
    输出:4
    解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
    

    示例 2:

    输入:nums = [0,1,0,3,2,3]
    输出:4
    

    示例 3:

    输入:nums = [7,7,7,7,7,7,7]
    输出:1
    

    提示:

    • 1 <= nums.length <= 2500
    • − 1 0 4 < = n u m s [ i ] < = 1 0 4 -10^4 <= nums[i] <= 10^4 104<=nums[i]<=104

    进阶:

    • 你可以设计时间复杂度为 O(n2) 的解决方案吗?
    • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

    在这里插入图片描述

    class Solution:
        def lengthOfLIS(self, nums: List[int]) -> int:
            if len(nums) == 0:
                return 0
            
            # 构建dp数组【同时也初始化了dp[0] == 1】 
            # dp[i] 表示以 nums[i] 为结尾的最长上升子序列的长度
            dp = [1] * len(nums)
    
            for i in range(len(nums)):
                for j in range(i):
                    if nums[j] < nums[i]:
                        dp[i] = max(dp[i], 1 + dp[j])
            
            print("dp = ", dp)
    
            return max(dp)
    

    输入数据:

    [10,9,2,5,7,101,18,3]
    

    打印结果:

    dp =  [1, 1, 1, 2, 3, 4, 4, 2]
    

    输出结果:

    4
    

    376. 摆动序列【中等】

    如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

    • 例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

    • 相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
      子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

    给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度 。

    示例 1:

    输入:nums = [1,7,4,9,2,5]
    输出:6
    解释:整个序列均为摆动序列,各元素之间的差值为 (6, -3, 5, -7, 3) 。
    

    示例 2:

    输入:nums = [1,17,5,10,13,15,10,5,16,8]
    输出:7
    解释:这个序列包含几个长度为 7 摆动序列。
    其中一个是 [1, 17, 10, 13, 10, 16, 8] ,各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
    

    示例 3:

    输入:nums = [1,2,3,4,5,6,7,8,9]
    输出:2
    

    提示:

    • 1 <= nums.length <= 1000
    • 0 <= nums[i] <= 1000

    八、最长公共子序列问题(Longest Common Sequence)

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    1143. 最长公共子序列【类似“72. 编辑距离”】

    给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

    一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

    • 例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。

    两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

    示例 1:

    输入:text1 = "abcde", text2 = "ace" 
    输出:3  
    解释:最长公共子序列是 "ace" ,它的长度为 3 。
    

    示例 2:

    输入:text1 = "abc", text2 = "abc"
    输出:3
    解释:最长公共子序列是 "abc" ,它的长度为 3 。
    

    示例 3:

    输入:text1 = "abc", text2 = "def"
    输出:0
    解释:两个字符串没有公共子序列,返回 0 。
    

    提示:

    • 1 <= text1.length, text2.length <= 1000
    • text1 和 text2 仅由小写英文字符组成。

    在这里插入图片描述
    在这里插入图片描述

    class Solution:
        def longestCommonSubsequence(self, text1: str, text2: str) -> int:
            m = len(text1)
            n = len(text2)
    
            # 构建dp数组
            dp = [[0] * (n + 1) for _ in range(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]
    

    718. 最长重复子数组【类似“72. 编辑距离”】

    给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

    示例:

    输入:
    A: [1,2,3,2,1]
    B: [3,2,1,4,7]
    输出:3
    解释:
    长度最长的公共子数组是 [3, 2, 1] 。
    

    提示:

    • 1 <= len(A), len(B) <= 1000
    • 0 <= A[i], B[i] < 100

    找两个数组的“公共”部分,实际上就是两个数组相同的数字。把这些公共的地方,在这张表格里用1来表示:
    在这里插入图片描述
    什么是“连续”的公共部分呢?其实就是在刚才我们标1的位置,找到一条或多条能从【左上】连到【右下】的线。注意,一定要是【左上】连到【右下】,如下图表示。

    那么,如何在动态更新中,记录每一条线的长度呢?答案是:每次先看一眼当前格子是否A、B对应位置的数字相等,然后看一下【左上】角的数字,将其+1,写在当前位置即可(如果左上角是空白,则说明左上角数字=0)。动态过程如下:

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    找到整张表格里最大的数字,就是我们能找到的最长路线长度了。

    class Solution:
        def findLength(self, nums1: List[int], nums2: List[int]) -> int:
            m = len(nums1)
            n = len(nums2)
    
            dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    
            result = 0
    
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if nums1[i - 1] == nums2[j - 1]:
                        dp[i][j] = dp[i - 1][j - 1] + 1
                        result = max(result, dp[i][j])
            
            return result
    

    九、其他

    152. 乘积最大子数组

    给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

    示例 1:

    输入: [2,3,-2,4]
    输出: 6
    解释: 子数组 [2,3] 有最大乘积 6。
    

    示例 2:

    输入: [-2,0,-1]
    输出: 0
    解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
    

    方法一:

    这道题目要我们求解连续的 n 个数中乘积最大的积是多少。这里提到了连续,笔者首先想到的就是滑动窗口,但是这里比较特殊,我们不能仅仅维护一个最大值,因为最小值(比如-20)乘以一个比较小的数(比如-10)
    可能就会很大。 因此这种思路并不方便。

    前面说了最小值(比如-20)乘以一个比较小的数(比如-10)可能就会很大 。因此我们需要同时记录乘积最大值和乘积最小值,然后比较元素和这两个的乘积,去不断更新最大值。当然,我们也可以选择只取当前元素。因此实际上我们的选择有三种,而如何选择就取决于哪个选择带来的价值最大(乘积最大或者最小)。

    关键点:同时记录乘积最大值和乘积最小值

    在这里插入图片描述

    class Solution:
        def maxProduct(self, nums: List[int]) -> int:
            pre_min = nums[0]
            pre_max = nums[0]
            result = nums[0]
    
            for i in range(1, len(nums)):
                curr_min = min(nums[i], pre_min * nums[i], pre_max * nums[i])   # 以 nums[i] 结尾的当前乘积最小的连续子数组的乘积
                curr_max = max(nums[i], pre_min * nums[i], pre_max * nums[i])   # 以 nums[i] 结尾的当前乘积最大的连续子数组的乘积
                result = max(result, curr_max)
                pre_min = curr_min
                pre_max = curr_max
                
            return result
    

    746. 使用最小花费爬楼梯

    数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。

    每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。

    请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯。

    示例 1:

    输入:cost = [10, 15, 20]
    输出:15
    解释:最低花费是从 cost[1] 开始,然后走两步即可到阶梯顶,一共花费 15 。
    

    示例 2:

    输入:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
    输出:6
    解释:最低花费方式是从 cost[0] 开始,逐个经过那些 1 ,跳过 cost[3] ,一共花费 6 。
    

    提示:

    • cost 的长度范围是 [2, 1000]。
    • cost[i] 将会是一个整型数据,范围为 [0, 999] 。

    方法一:动态规划

    在这里插入图片描述

    class Solution:
        def minCostClimbingStairs(self, cost: List[int]) -> int:
            n = len(cost)
            dp = [0] * (n + 1)
            for i in range(2, n + 1):
                dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
            return dp[-1]
    

    方法二:动态规划

    dp[i] 含义:到第 i 节阶梯花费的最小体力(包含当前阶梯)

    转移方程:dp[i] = min(dp[i - 2], dp[i - 1]) + cost[i]

    从前两节阶梯爬到当前阶梯 或 从前一节阶梯爬到当前阶梯,两者取最小值,再加上当前阶梯花费体力

    返回min(dp[-1], dp[-2]),因为倒数第二节阶梯也可以直接走到终点,看哪个花费体力更少

    class Solution:
        def minCostClimbingStairs(self, cost: List[int]) -> int:
            n = len(cost)
            dp = [0] * n
            dp[0], dp[1] = cost[0], cost[1]
            for i in range(2, n):
                dp[i] = min(dp[i - 2], dp[i - 1]) + cost[i]
            return min(dp[-1], dp[-2])
    

    方法三:动态规划

    读题是很重要的。这个地方的题目,我来翻译翻译什么叫白话文。

    从第0层或者第一层开始爬楼梯,在某一层停留就要付出当前层次的代价,每次都能爬一层或者两层,直到把整个楼层爬完(就是把整个数组遍历完之后还要再来一位数字)。

    状态转移方程就是当前层次比较前两层和前一层,看那个数值小,就选择那个数值小的然后加上自己。

    我们从第二层开始判断,也就满足了题目的要求,可以从第零层或者第一层开始。。

    class Solution:
        def minCostClimbingStairs(self, cost) -> int:
            cost.append(0)
            n = len(cost)
            dp = [0]*n
            dp[0] = cost[0]
            dp[1] = cost[1]
            for i in range(2, n):
                dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
            return dp[-1]
    

    剑指 Offer 46. 把数字翻译成字符串

    给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

    示例 1:

    输入: 12258
    输出: 5
    解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
    

    提示: 0 < = n u m < 2 31 0 <= num < 2^{31} 0<=num<231


    方法一:动态规划

    在这里插入图片描述
    在这里插入图片描述

    class Solution:
        def translateNum(self, num: int) -> int:
            s = str(num)
            n = len(s)
    
            # 构建dp数组
            dp = [0 for _ in range(n + 1)]
    
            # 初始化dp边界
            dp[0] = 1
            dp[1] = 1
    
            # 状态转移
            for i in range(2, n + 1):
                a = int(s[i - 2]) * 10 + int(s[i - 1])
                if 10 <= a <=25:
                    dp[i] = dp[i - 2] + dp[i - 1]
                else:
                    dp[i] = dp[i - 1]
            
            return dp[-1]
    
    class Solution:
        def translateNum(self, num: int) -> int:
            s = str(num)
            n = len(s)
    
            if len(s) == 1:
                return 1
    
            # 构建dp数组
            dp = [0] * n
    
            # 初始化dp边界
            dp[0] = 1
            b = int(s[0]) * 10 + int(s[1])
            if 10 <= b <= 25:
                dp[1] = 2
            else:
                dp[1] = 1
    
            # 状态转移
            for i in range(2, n):
                b = int(s[i - 1]) * 10 + int(s[i])
                if 10 <= b <= 25:
                    dp[i] = dp[i - 1] + dp[i - 2]
                else:
                    dp[i] = dp[i - 1]
            
            return dp[-1]
    



    参考资料:
    动态规划之01背包问题
    动态规划0—1背包问题
    【动态规划】01背包问题
    【动态规划】一次搞定三种背包问题
    动态规划之背包问题系列
    动态规划为什么这么难?多做题对熟练掌握动态规划有用吗?

    展开全文
  • 前言在量化分析工具QTYX上,我们新增了双形态的识别功能,不少星球小伙伴结合这个方式选出了上涨初期的个股,同时根据实战应用中的一些经验反馈给我了不少需求,大家一起来优化这个策略体系,不断...

    40e3d7b840234fe6634a8c18c503e4f0.png


    017707bedff10aef7f00596e41395564.png

    前言

    28b8f882423d50fc40f148c06399ed97.png

    在量化分析工具QTYX上,我们新增了双底形态的识别功能,不少星球小伙伴结合这个方式选出了上涨初期的个股,同时根据实战应用中的一些经验反馈给我了不少需求,大家一起来优化这个策略体系,不断完善这个体系的同时也能帮助大家一起赚钱,一举两得!

    目前这个选股思路在实战中效果整体不错,我打算沿着这个策略逐步深入优化。这个过程中是一种持续迭代的过程,我们会不断地调整策略算法的细节,因此我们先提供单独的版本供大家学习和调试,降低大家的运行的难度,提高大家二次更改的灵活度,等这个策略稳定后会更新到量化分析工具QTYX中。


    6ba148edcec6779df22097b1056599cb.png

    使用小技巧

    b3d09e661f681616255e142da64560a1.png

    首先建议大家尽量把参数设置得苛刻一点,宁缺毋滥一点。

    比如【有效突破当天涨跌幅%】【有效突破偏差】设置得低一点,会出现很多以下走势的个股,虽然也是双底突破,但是非常弱。

    f70d50582bc7e40eba013e4ba1bd8e72.png

    比如【有效突破当天涨跌幅%】【有效突破偏差】设置得高一点,可以过滤掉很多假突破真诱多的股票,选出来的强势股概览会大幅提高。

    a81f38c3bba47c24b5be97dea94837ca.png

    31b9e495423b2441037d15ca3bc7f696.png

    主要原因是出现双底走势是强势股的必要条件,而不是充分条件,所以尽量利用苛刻的参数去由形态反向搜索强势股,这样选中的概率更高。

    另外也要配合一定的仓位管理和止损策略,当出现判断失误的时候一定要果断止损。


    feaec1b31d736c6a09bcc4aef6813f09.png

    叠加跳空缺口

    8875ad423dfa13cae3c2174a9868e2c3.png

    这次我们优化功能是在双底形态识别的同时判断该股近期是否有向上跳空缺口配合出现,如果有的话可以侧面说明该股的强势。

    跳空缺口是K线形态中一种威力很大的形态,它是指相邻的两根K线之间出现了没有交易的空白区间,当今日最低价与昨日最高价之间没有重合部分,称为向上缺口,当今日最高价与昨日最低价之间没有重叠部分,称为向下缺口。

    4412053fa3ebafc9d846061721b44d9b.png

    股价留下缺口,不仅仅是当日投资者激烈情绪的反映,在很多情况下,这种缺口对于判断后市是具有一定意义的。

    我们设计了一个策略去判断跳空缺口,这里我们的算法思路如下:

    • 如果今日是上涨趋势,今日的最低价大于昨日的最高价,并且达到设定的阈值时为向上跳空缺口;

    • 如果今日是下跌趋势,昨天最低价大于今日最高价,并且达到设定的阈值时为向下跳空缺口。

    光是跳空幅度大于阈值还不够,我们还结合成交量及当日涨跌幅去叠加判断,毕竟底部出现放量跳空上涨时,说明该股更加强势。

    比如以下参数设置的叠加条件是:成交量大于近期平均值*1.1;涨幅大于2%。

    # 定义跳空缺口识别参数
    DEF_JUMP_THR = 0.01  # 跳空阈值 收盘价中位数*0.01
    DEF_CHANGE_RAT = 2 # 当日上涨幅度 %
    DEF_VOLUME_RAT = 1.1 # 成交量均值比例

    469d0890d4f8e9d4b86bd0bed7053383.png

    什么是双底形态

    9ae7559aae5300ffa563fb1497261241.png

    双重底也称“W底”,是指股票的价格经过一段下跌后,形成一个低点后展开反弹,随后再次回落,在上一个低点附近形成新的低点,此后股价再次往上运行,这样就形成了两个底部,成为双重底。

    两个跌至最低点的连线称为“支撑线”。

    两个低点之间的高点价格称为“颈线”价格。

    通常放量突破颈线时是一个不错的买点。

    突破后会有两种形态:第一种是突破后直接快速拉升;第二种是突破之后缩量回踩颈线位置附近,确认突破有效后再快速拉升。

    c82a65bf7aeef17d5d9c889c86d37eb7.png

    4fc6eeb7c24b70d986318fd88a64222d.png

    识别形态的算法分析

    4d9177682588150be56cb49bd08effbd.png

    ec684f97c7b4932852d8bc499c333e34.png

    如上图所示,我们以个股的收盘价时间序列为分析数据。当前交易日期为终点,往前从历史交易日中选择两个连续区间。

    这两个区间先按完全相等的范围设定,然后增加一个区间叠加变量,这个变量的作用是可以进一步去过滤像头肩底或者V型底的形态。

    当然也可以动态去划分,划分的规则可以根据市场的整体走势来设定。

    然后按以下步骤分析:

    找区间1的极小值,为左底

    找区间2的极小值,为右底

    找左底与右底之间区域的极大值

    比较左底与右底的涨幅,是否相差<3%(参数可调)

    当前交易日收盘价是否突破颈线位>3%(参数可调)

    当前交易日是否为首次突破颈线位

    当前交易日突破时的涨幅是否大于>3%(参数可调)

    当前交易日突破时伴随的成交量是否大于近期平均成交量的20%(参数可调)

    203d6a40b087e09db184227e412c3734.png

    如何使用形态识别功能

    de7927c1f487ffef225ab276db830e8f.png

    代码中总共开放了8个参数:选取K线范围、选取中间区域误差、双底低点之间误差、有效突破确认的幅度、有效突破当天涨跌幅、有效突破成交量阈值

    、检测双底突破是否带跳空缺口。

    DOUBOT_DETECT_DATES_RANGE = 60, # 往前寻找的范围
    DOUBOT_DETECT_DATES_MID=30,  # 区间划分中间点
    DOUBOT_DETECT_DATES_VAR = 5,  # 可变区间
    DOUBOT_MIN_DIFF_FACTOR = 0.03,  # 最小值误差
    DOUBOT_BREAK_PCTCHG_VAR = 0.01,  # 有效突破当天涨跌幅
    DOUBOT_BREAK_RATIO_FACTOR = 0.03,  # 有效突破偏差
    DOUBOT_BREAK_VOLUME_THR = 0.03  # 放量突破比例 默认超过平均的30%
    DETECT_JUMP_GAP_ENABEL = True # 检测双底突破是否带跳空缺口 True为检测

    比如有效突破成交量阈值表明,在突破当天的成交量要高于“选取K线范围”内成交量均值的百分之X以上。

    点击确认后,开始自动识别,当前分析产生的结果有以下几种:

    1. 形态无效: 滤除股票 东方生物,代码 sh.688298

    2. 形态有效: 股票中红医疗, 代码sz.300981 分析结果如下:

      a) 双底形态判断有效:左底 2021-06-22/102.6元; 右底 2021-07-26/101.63元; 中顶 2021-07-15/116.18元;

      b) 未形成有效突破幅度!

    3. 形态有效: 股票辉煌科技, 代码sz.002296 分析结果如下:

      a) 双底形态判断有效:左底 2021-07-01/6.72元; 右底 2021-07-28/6.62元; 中顶 2021-07-22/7.16元;

      b) 双底形态突破幅度有效:当前收盘价 7.39元; 颈线价格 7.16元; 

      c) 双底形态突破放量有效:当前成交量 87619.64手; 平均成交量 62783.05307692308手;

    4. 形态有效: 股票民生控股, 代码sz.000416 分析结果如下:

      a) 双底形态判断有效:左底 2021-07-28/3.5元; 右底 2021-10-20/3.53元; 中顶 2021-09-13/4.04元;

      b) 双底形态突破幅度有效:当前收盘价 4.27元; 颈线价格 4.04元; 

      c) 当日为首次突破!!!--双底形态突破涨幅有效:当前涨幅 0.1005%; 

      d) 双底形态突破放量有效:当前成交量 174243手; 平均成交量 51667.8813559322手; 

      e) 检测[sz.000416 民生控股]近期向上跳空缺口

      f) 检测到2021-10-22出现向上跳空缺口, 跳空能量为4.23!

    分析结果会自动存入txt格式的日志中和csv格式的表格文件中。

    为了保险起见,大家筛选出来的股票尽量人工确认一番,然后结合其他角度的分析去决定是否购买。

    e24a89a936b1940dec3e343dfc3fb918.png

    量化机器人远程提醒

    9e6002482f1df5f50fc14a507bd269e9.png

    由于筛选全市场4000多只股票耗时比较长,通常我是让服务器自动运行的,运行完成后,以邮件方式通知到我手机微信上(只需要在微信上开启QQ邮箱提醒功能即可),让我去看运行的结果。

    具体介绍可以看这篇文章:

    适合加班族的量化选股场景——还没到家就收到量化机器人的选股报告

    d1be4ff204c332ea3c35d785b261e420.png

    10月25日至11月1日加入星球者,可以免费体验这个场景服务,我用我搭建的云服务器,每天20点远程推送双底形态识别结果到你的手机QQ邮箱,限10人先到先得。

    说明

    1. 我们会把完整的源码上传到知识星球《玩转股票量化交易》中,帮助小伙伴们更好地掌握这个方法。

    2. 想要加入知识星球《玩转股票量化交易》的小伙伴记得先微信call我获取福利,名额有限先到先得!

    8b09cf2e0ef8389a795272fcd55e5b05.png

    元宵大师的量化交易书籍开售!!
    京东、当当、天猫有售!!

    7372cec1a7690f50b8207cc1facefb2c.png

    展开全文
  • b站视频:路飞IT学城 ...文章目录#91 钢条切割问题自底向上实现#92 钢条切割问题:重构解#93 最长公共子序列#94 最长公共子序列:实现#95 欧几里得算法#96 RSA算法介绍#97 RSA算法测试#98 算法课程总结 个人博客 ...
  • java类java类分为普通类和抽象类,接口,上一节我大概讲了java类的一般格式,今天将抽象类...解析:抽象类往往用来表征对问题领域进行分析、设计中得出的抽象概念,是对一系列看上去不同,但是本质上相同的具体概念...
  • 数据仓库的实现方法

    2021-09-05 23:41:21
    从整体的角度来看,数据仓库的实现方法主要顶向下法、自底向上法和联合方法。 1.顶向下法 在该方法中,首先应找出数据仓库解决方案所要满足的商业需求,把商业需求视为实现数据仓库的首要任务。数据仓库是一...
  • 本篇主要程序设计方法学,以体育竞技分析为例,介绍顶向下的设计和自底向上的执行。以第三方库自动安装脚本为例,整体理解代码设计思路和os库的使用。 读完本篇,你将了解: 1.方法论 理解并掌握一批Python程序...
  • PAGE 实 验 报 告 课程名称: 数据结构 实验名称: 赫夫曼编码及应用 院 (系): 计算机与通信工程学院 专业班级: 计算机科学与技术 姓 名: 学 号: 指导教师: 2020 年 5 月... 在选择存储结构时,选择了链式存储结
  • 算法复习——贪心策略篇之活动选择问题 以下内容主要参考中国大学MOOC《算法设计与分析》,墙裂推荐希望入门算法的童鞋学习! 1. 问题背景 ​ 假设有一个会场,可以举行公司年会、婚礼宴请、生日聚会和学术研讨等...
  • 导航按钮点击 如果你刚刚用了setSupportActionBar()方法,那你可以在选择id的时候调用导航按钮,如果没有你就可以下面的方法: BottomAppBar bar = (BottomAppBar) findViewById(R.id.bar); bar....
  • 3、打开“我的电脑”窗口中“(C:)”盘,看一下窗口中的内容,单击工具栏上的“向上”按钮,回到“我的电脑”,再打开“(D:)”盘,看一下窗口中的内容,点“向上”按钮,回到“我的电脑”; 4、看一下地址栏中的...
  • 无人驾驶 | 自动驾驶技术和机器人技术的对比

    千次阅读 多人点赞 2021-01-09 13:06:36
    运动底座向上提供的基本接口包括:线速度,角速度或曲率控制, 查询当前里程计信息,完成上层对运动底座的控制和信息查询。 2. 硬件平台 运算单板是硬件部分,与运算单板同层的其它模块,都是感知单元,感知单元涵盖...
  • 运动底座向上提供的基本接口包括:线速度,角速度或曲率控制, 查询当前里程计信息,完成上层对运动底座的控制和信息查询。 2. 硬件平台 运算单板是硬件部分,与运算单板同层的其它模块,都是感知单元,感知单元涵盖...
  • 主要功能 下拉刷新、滑动到底部自动加载下页数据; 可以方便添加Header和Footer; 头部下拉样式可以自定义; 具备item点击和长按事件。 网络错误加载失败点击Footer重新请求数据; 可以动态为FooterView赋予不同...
  • 概要可以通过对每个结点运行一次上一章中的最短路径算法,来解决所有结点对的最短路径问题,但效率较低,本章考虑的是用新的算法更高效的解决此问题本章使用邻接矩阵来表示图,边的权重也存储在一个矩阵 W 中,算法...
  • macd双选股公式

    2021-01-13 03:50:01
    常用的MACD信号为红柱、绿柱、金叉、死叉和顶、背离。今天股掌资尚想给大家分享一下MACD炒股运用技巧。首先:我们如何操作才能让这个指标更加可靠,最好的办法就是等待双金叉的出现,这样要比一个金叉稳定得多。...
  • 算法习题——选择

    2021-05-23 04:12:46
    求解某一类问题的算法是唯一的(如:冒泡排序可以用:穷举法、递归)Ⅱ.算法必须在有限步操作之后停止Ⅲ.算法的每一步操作必须是明确的,不能有歧义或含义模糊Ⅳ.算法执行后一定产生确定的结果A.1个 B.2个 C.3个 D.4个...
  • 为了缩短信息通路, 该模型利用低层精确的定位信息提升特征金字塔, 创建了自底向上的路 径增强。为了恢复候选区域和所有特征层之间被破 坏的信息通路, Liu 等[41] 开发了自适应特征池化, 用 来汇聚每个候选区域所有...
  • 算法主要的任务概述

    2021-09-25 19:19:26
    机器学习和深度学习所有的算法可以简单的说就是解决两类问题: 回归拟合(regression):该问题的目的是为了预测未来,比如说股票的涨跌,抖音访客数点赞数的预测,未来气候的预测,温度的预测等等还可以进行工业...
  • } } ZBottomSheetAdapter解释说明 本适配器的主要功能是用于底部评论弹窗的图片recyclerview的adapter 该adapter有两种ItemViewType(0:添加图片,1:查看图片) //对外暴露的监听方法,具体方法见adapter的holder ...
  • 贪心选择算法为算法分析中一种常用算法,通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态下某种意义的最好选择,即贪心选择。希望通过每次所作的贪心选择导致最终结果是问题的一个最优解。这种...
  • 圆弧形成的过程比较漫长,所以,投资者不要过早介入,可以选择在放量突破颈线时买入。 五、V形 V形也称为“尖”,它是指股价在下跌过程中,开始加速下跌,几乎没有像样的反弹,最后,股价在最猛烈的下跌后...
  • 调研-知识图谱构建

    2021-07-20 13:59:13
    知识图谱主要顶向下(top-down)与自底向上(bottom-up)两种构建方式。 顶向下指的是先为知识图谱定义好本体与数据模式,再将实体加入到知识库。该构建方式需要利用一些现有的结构化知识库作为其基础知识库,...
  • 文章目录第五章 集成测试5.1概述5.1.1定义、目的、内容、检查方面5.1.2层次5.1.3原则5.2集成测试策略5.2.1非增量式5.2.2增量式5.2.2-1顶向下增量式测试5.2.2-2自底向上增量式测试5.2.2-3三明治增量式测试(混合...
  • 但究竟怎样的价格是“最便宜”,或称“”,并没有明确的标准。如何精准判断市场进入底部?在和各位投资者分析如何判断股市底部之前,要和大家先讲述一个理念:任何预测预想出来的底部都不是底部,底部是走出来的,...
  • (2008H-2001H=07H)A. 05H B. 06H C. 07H D. F7H E. F8H F. F9H17.在存储器堆栈中,保持不变的是 C 。(栈指针随着数据的进出而增减,栈顶和栈中(有这个名词吗?)会随之变化。)A. 栈顶 B.... 栈 D...
  • 点击上方“3D视觉工坊”,选择“星标”干货第一时间送达前言 MV3D-Net 融合了视觉图像和激光雷达点云信息;输入数据有三种,分别是点云俯视图、点云前视图和RGB图像。通过特征...
  • C语言选择题及答案

    2021-05-19 12:58:03
    C语言选择题及答案选择题答案与解析:1.C。【解析】根据二叉树的性质及定义,一棵深度为k 且有2k-1个结点的二叉树为满二叉树。满二叉树的叶子结点为最后一层的结点数,又根据满二叉树的性质,在满二叉树的第i层上...
  • 业务逻辑需要中间件支撑,涉及透明化集成、资源弹性、愈能力等,帮助用户轻松构建应用,但是对于应用逻辑的构建无能为力,因为这是业务领域的问题。 还有一个大大的疑问,就是上面只是说明了需求来源,但是没有说...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,617
精华内容 16,246
关键字:

自底向上的主要问题是()的选择

友情链接: Noto_Sans.zip