算法Day09-动态规划之最长递增子序列

水深无声 2022-12-03 01:32 147阅读 0赞

### 动态规划之最长递增子序列 ###

*  基本概念
 *  动态规划解法
 *  二分查找解法

# 基本概念 #

*  动态规划的通用技巧 **: 数学归纳思想**
 *  最长递增子序列**LIS**问题:
    
     *  动态规划解法. 时间复杂度是 O(N2)
     *  二分查找解法. 时间复杂度是  O ( N log ⁡ N ) O(N\\log N) O(NlogN)
 *  **注意:** 子序列和子串之间的区别
    
     *  子序列不一定是连续的
     *  子串一定是连续的

# 动态规划解法 #

*  **动态规划的核心思想:** 数学归纳法

>  *  想要证明一个数学结论成立:
>     
>      *  先假设这个结论在  k < n k < n k<n 时成立
>      *  然后证明  k = n k = n k=n 时此结论也成立
>      *  那么就说明这个结论对于  k k k 等于任何数时都是成立的

*  **动态规划算法:** 需要一个**DP**数组
    
     *  可以假设  d p \[ 0 , . . . , i − 1 \] dp\[0,...,i - 1\] dp\[0,...,i−1\] 都已经计算出来
     *  通过这些结果计算出 d p \[ i \] dp\[i\] dp\[i\]
 *  **最长递增子序列LIS问题:**
    
     *  首先要定义清楚  d p dp dp 数组的含义
     *  要清楚  d p \[ i \] dp\[i\] dp\[i\] 的值代表的含义
 *  **定义:**  d p \[ i \] dp\[i\] dp\[i\] 表示以  n u m s \[ i \] nums\[i\] nums\[i\] 这个数结尾的最长递增子序列的长度
 *  根据定义,可知最终结果的子序列的最大长度就是**dp**数组中的最大值

int res = 0;
    for (int i = 0; i < dp.size(); i ++) { 
    	res = Math.max(res, dp[i]);
    }
    return res;

*  设计动态规划算法正确计算每个  d p \[ i \] dp\[i\] dp\[i\] : 使用数学归纳法思考如何进行状态转移
    
     *  根据对**dp**数组的定义,已知  d p \[ 0 , . . . , 4 \] dp\[0,...,4\] dp\[0,...,4\] 的结果,要求  d p \[ 5 \] dp\[5\] dp\[5\] 的值,也就是要求  n u m s \[ 5 \] nums\[5\] nums\[5\] 为结尾的最长递增子序列
     *   n u m s \[ 5 \] = 3 nums\[5\]=3 nums\[5\]=3,因为是递增子序列,只要找到之前结尾比**3**小的递增子序列,然后将**3**接到最后,就可以形成一个新的递增子序列,并且这个新的序列长度会增加**1**
     *  形成的子序列有多种,只是需要最长的,将最长子序列的长度作为  d p \[ 5 \] dp\[5\] dp\[5\] 的值
    
        for (int j = 0; j < i, j++) { 
        	if (nums[i] > nums[j]) { 
        		dp[i] = Math.max(dp[i], dp[j] + 1);
        	}
        }
    
     *  使用数学归纳法,可以计算出其余的**dp**数组的值
    
        for (int i = 0; i < nums.length; i++) { 
        	for (int j = 0; j < i; j++) { 
        		if (nums[i] > nums[j]) { 
        			dp[i] = Math.max(dp[i], dp[j] + 1);
        		}
        	}
        }
    
     *  **dp**数组应该全部初始化为**1,** 因为子序列长度最少也要包含自己,所以最小长度为**1**而不为**0**
 *  **最长递增子序列完整代码:**

public int lengthOfLIS() { 
    	int[] dp = new int[nums.length];
    	// dp数组全部初始化为1
    	Arrays.fill(dp, 1);
    	for (int i = 0; i < nums.length; i++) { 
    		for (int j = 0; j < i; j++) { 
    			if (nums[i] > nums[j]) { 
    				dp[i] = Math.max(dp[i], dp[j] + 1);
    			}
    		}
    	}
    	int res = 0;
    	for (int i = 0; i < dp.length(); i++) { 
    		res = Math.max(res, dp[i]);
    	}
    	return res;
    }

*  最长递增子序列的DP数组算法的时间复杂度为**O(N2)**
 *  **动态规划设计流程:**
    
     *  **首先明确DP数组所存数据的含义**
        
         *  这步很重要,如果含义不明确,会导致后续步骤计算混乱
     *  **然后根据DP数组的定义,计算出  d p \[ i \] dp\[i\] dp\[i\]**
        
         *  运用数学归纳法的思想,假设  d p \[ 0 , . . . , i − 1 \] dp\[0,...,i-1\] dp\[0,...,i−1\] 的值都是已知,根据  d p \[ 0 , . . . , i − 1 \] dp\[0,...,i-1\] dp\[0,...,i−1\] 的值求出  d p \[ i \] dp\[i\] dp\[i\]
            
             *  一旦完成这个步骤,整个题目就基本解决了
             *  如果无法完成这一步骤,就要重新思考**DP**数组的定义
             *  或者可能是DP数组存储的信息不完全,无法推导出下一步的答案,就需要将**DP**数组扩大成为二维数组甚至三维数组
     *  **最后确定问题的base case**
        
         *  使用**base case**初始化数组,保证算法正确运行

# 二分查找解法 #

*  最长递增子序列的二分查找解法的算法时间复杂度为  O ( N log ⁡ N ) O(N\\log N) O(NlogN)
 *  最长递增子序列和一种叫作**patience game**的纸牌游戏有关,有一种排序算法就叫做**耐心排序patience sorting**
 *  **场景分析:** 给定一排纸牌,然后从左到右像遍历数组那样一张一张处置这些纸牌,最终将这些纸牌分成若干堆
    
     *  只能将点数小的牌压到点数大的牌上
     *  如果当前牌点数较大没有可以放置的堆,则新建一个堆,将这张牌放置进去
     *  如果当前牌有多个堆可供选择,则选择最左边的堆放置
        
         *  选择最左边的堆放置的原因是为了保证堆顶的牌有序
 *  按照上述规则,可以算出最长递增子序列,牌堆数就是最长递增子序列的长度
 *  **二分查找算法求解最长递增子序列:**
    
     *  将处理扑克牌的过程使用编程的方式表达出来
     *  因为每次处理一张扑克牌要找到一个合适的牌堆顶放置,牌堆顶的牌是有序的.所以可以使用二分查找
     *  使用二分查找来搜索当前牌应该放置的位置

public int LengthOfLIS(int[] nums) { 
    	int[] top = new Int[nums.length];
    	// 牌的堆数初始化为0
    	int piles = 0;
    
    	for (int i = 0; i < nums.length; i++) { 
    		// 需要处理的牌
    		int poker = nums[i];
    
    		int left = 0, right = piles;
    		while (left < right) { 
    			int mid = left + (right -left) / 2;
    			if (top[mid] > poker) { 
    				right = mid;
    			} else if (top[mid] < poker) { 
    				left = mid + 1;
    			} else { 
    				right = mid;
    			}
    		}
    		// 没有找到合适的牌堆则新建一个牌堆
    		if (left == piles) { 
    			piles++;
    		}
    		// 选择最左边的牌堆放置
    		top[left] = piles;
    	}
    	// 牌堆数就是最长递增子串的长度
    	return piles;
    }

*  **二分查找解法:**
    
     *  首先涉及数学证明,要证明出按照这些规则的执行,就能得到最长递增子序列
     *  其次是二分查找算法的应用,要理解二分查找方法的细节
 *  **动态规划设计方法:**
    
     *  假设之前的答案为已知
     *  利用数学归纳法的思想正确进行状态转移
     *  最后得到答案

>  *  **动态规划解法:**
> 
>     def lengthOfLIS(self, nums : List[int]) -> int:
>     	n = len(nums)
>     	dp = [1 for x in range(0, n)]
>     	for i in range(0, n):
>     		for j in range(0, i):
>     			if nums[i] > num[j]:
>     				dp[i] = max(dp[i], dp[j] + 1)
>     	res = 0
>     	for temp in dp:
>     		res = max(temp, res)
>     	return res
> 
>  *  **二分查找解法:**
> 
>     def lengthOfLIS(self, nums : List[int]) -> int:
>     	top = []
>     	# 牌堆初始化为0
>     	piles = 0
>     	# num为需要处理的牌
>     	for num in nums:
>     		left, right = 0, 
>     	while left < right:
>     		mid = left + (right - left) / 2
>     		# 搜索左侧边界
>     		if top[mid] > num:
>     			right = mid
>     		# 搜索右侧边界
>     		elif top[mid] < num:
>     			left = mid + 1
>     		else
>     			right = mid
>     	if left == piles:
>     		# 如果没有找到合适的牌堆,就新建一个牌堆
>     		piles += 1
>     	# 将该牌放到新建的牌堆顶
>     	top[left] = num
>     	# 牌堆数就是最长递增子序列的长度
>     	return piles