【初级算法】动态规划入门学习

淩亂°似流年 2022-11-13 09:26 210阅读 0赞

一、前言

> 在去年暑假的时候，一个朋友建议我开始每天三道LeetCode刷题。但是由于刚开始学习Java框架以及C和数据结构很久没有碰了，于是就一心学习spring去了，忽略了算法的重要性。最近春招以及考研复习数据结构，才发现算法的重要性。因此，开始了算法的学习。

二、准备工作

注：为便于梳理框架，我会进行在准备工作处进行该系列的整理，如果只想快速看本主题，请点击链接。

1.  基础语法知识  
    **C语言篇**  
    （1）基础类型使用，控制逻辑使用  
    （2）STL库的基本使用  
    （3）algorithm库的简单使用（结构体排序、数组排序、查找等）  
    （4）字符串与数组、循环的灵活使用  
    （5）递推、递归、迭代  
    （6）常见数据结构（线性表、字符串、树、图）的使用  
    **Java篇**  
    （1）八大类型+String+数组的基本使用，以及OOP思维  
    （2）list、map、set的基本使用（遍历、排序、查找操作）  
    （3）Collections、Arrays工具类的基本使用  
    （4）递归、迭代  
    （5）常见数据结构的Java表示
2.  基本路线  
    （1）数组类、字符类、链表的熟悉  
    （2）分治策略  
    （3）贪心、回溯  
    （4）DP、NP  
    （5）数学、概率  
    （6）网络流、搜索等  
    以上为初级简单阶段的规划，详细的如下（算法工程师所学）的参考：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center]
3.  学习策略

（1）LeetCode的初级、中级、高级算法篇，刷题＋看题解  
（2）书本：数据结构+课本（算法导论）+剑指offer  
（3）总结

三、动态规划（初级篇）

1.什么是动态规划

> 动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果

首先，得明白动态规划是进行最优解求解的，贪心也是进行求最优解但略有不同（在选择策略方面）。

2.动态规划的步骤  
（1）确定状态  
（2）确定状态转移  
（3）确定初始和边界条件  
（4）计算结果（根据需要是否进行存储具体信息）

ps：和递归有点类似，个人感悟：提升寻找规律，数学归纳能力很重要，学会分析题目的内因外果以及联系！！

3.典型例题  
（1）爬楼梯  
分析：  
先考虑状态，确定第i个的值（最优解，此处无需考虑）当dp\[i\]（以下都采用dp数组进行确定第i+1个值的最优解或最大利益）可以由i-1爬一个梯子也可以由i-2爬两个梯子，因此很容易得到递推式 dp\[i\] = dp\[i-1\]+dp\[i-2\] ；有了递推式，那么就只需要确定边界即可。

package dp;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /* * 爬楼梯 * */
    public class ClimbLadder { 
    
    	// 递归办法
    	public int climbStairs(int n) { 
    		if(n==1||n==2) { 
    			return n;
    		}else { 
    			return climbStairs(n-1)+climbStairs(n-2);
    		}
    	}
    	
    	// 尾递归
    	// 时间：100%，内存34%
    	 public static int climbStairs3(int n) { 
    	        return Fibonacci(n, 1, 1);
    	    }
    
    	    public static int Fibonacci(int n, int a, int b) {  // a为第一项(n-2)情况数，b为第二项(n-2)情况数 ,n为第几阶，，迭代的感觉
    	        if (n <= 1)
    	            return b;
    	        return Fibonacci(n - 1, b, a + b);// 少一阶台阶，
    	    }
    	    
    	    // 迭代 100%,60%左右
    	 public int c(int n) { 
    		 
    		 
    		 if(n==1||n==2) { 
    			 return n;
    		 }else { 
    			 int a=1,b=2,c = 0;
    			 for(int i=3;i<=n;i++) { 
    				 c= a+b;
    				 a = b;
    				 b = c;
    			 }
    			 return c;
    		 }
    // return n;
    	 }
    	    
    	
    
    	// 非递归 => 内存优化 在外部声明(数组（动态数组）、map都可）？判断即可
    // private 时间：100% 内存：95% 
    	public int climbStairs2(int n) { 
    		
    		if(n==1||n==2) { 
    			return n;
    		}else { 
    			List<Integer> cache = new ArrayList<>();
    			
    			cache.add(1);
    			cache.add(2);
    			
    			int i=3;
    			while(i<=n) { 
    				
    				cache.add(cache.get(i-2)+cache.get(i-3));
    				
    				i++;
    			}
    			
    			return cache.get(n-1);
    			
    		}
    // return n;
    	}
    	
    	
    	public static void main(String[]args)
    	{ 
    		ClimbLadder c = new ClimbLadder();
    		
    		for(int i =1;i<45;i++) { 
    			 long start = System.currentTimeMillis();
    			 
    			 System.out.print(c.climbStairs(i));
    		     
    			 long end = System.currentTimeMillis();
    			 
    			 System.out.print(" 用时"+(end-start)+";");
    		 
    			 
                 long start2 = System.currentTimeMillis();
    			 
    			 System.out.print(c.climbStairs2(i));
    		     
    			 long end2 = System.currentTimeMillis();
    			 
    			 System.out.println(" 用时:"+(end2-start2));	 
    		}   
    	}
    }

2.最长连续子序列（不连续，正数相加即可）  
同样道理：  
确定状态：dp\[i\]表示的什么（该处最大值）  
确定状态转移：当第i-1项为负数时，此时会导致最大值变小需要转换状态为nums\[i\]，该当前项的值，即从此处开始记录。如果非负则可加上该处继续连续着走。即可得到关系式 dp\[i\] = nums\[i\]+Math.max(dp\[i-1\],0);  
确定边界：第一项

package dp;
    /** * * @author LYF * * 最长连续子序列 * * 动态规划标准步骤 * 1.确定（定义）状态 * 2.状态转移 * 3.确定初始和边界 * 4.计算结果 * */
    public class MaxSequenceSum { 
    	
    	
    	// 时间95%，内存6%
    	public int maxSubArray(int []nums) { 
    		
    		// 1.确定状态
    		// 设定 dp[i]为前i+1最大和，那么dp[i-1]
    		
    		// 2.状态转移
    		// 当dp[i-1]为负时，则进行转移dp[i]就设为新的nums[i],因为dp[i]为负只会累加更小
    		
    		// 3.边界则是dp[0]为本身
    		
    		int len = nums.length;
    		int[] dp = new int[len];
    		dp[0] = nums[0];// 定义初始条件,前1个数据最大
    		int max = dp[0];// 刚开始最大只能为第一个数
    		for(int i =1;i<len;i++) {  // 开始进行从i到len的情况测试，如果需要记录0-n之间具体情况，可进行打表
    			if(dp[i-1]<0) {  // 前i-1+1（数组从0开始）项最大值
    				// 小于0，只会越加越少，因此进行状态转移，将序列起点移动到i
    				dp[i] = nums[i];
    			}else { 
    				dp[i] = dp[i-1]+nums[i];// 否则进行累计
    			} // 简化代码： dp[i] = nums[i]+Math.max(dp[i-1],0); 
    			
    			max = Math.max(dp[i], max);// 比较此次最大
    		}
    		
    		return max;
    	}
    	
    	// 优化
    	
    	// 思考内存上面怎么优化？
    	// 减少数组方面的开销，使用单个变量记录dp? => 可行吗？,不难发现该题只需要
    	// 求得最大值，无关每个i具体的最大值以及起始点，因此采用两个变量记录递推（i-1和i)就行
    	// 
    	
    		public int maxSubArray2(int []nums) { 
    			
    			int len = nums.length;
    // int[] dp = new int[len];
    			int dp0 = nums[0],dp1=0;// 定义初始条件,dp0为i-1项，dp1为当前项
    			int max = dp0;// 刚开始最大只能为第一个数
    			for(int i =1;i<len;i++) {  // 开始进行从i到len的情况测试，如果需要记录0-n之间具体情况，可进行打表
    				
    				if(dp0<0) {  // 前i-1+1（数组从0开始）项最大值
    					// 小于0，只会越加越少，因此进行状态转移，将序列起点移动到i
    					dp1 = nums[i];
    					dp0 = dp1;
    				}else { 
    					dp1 = dp0+nums[i];// 否则进行累计
    					dp0= dp1;//为下一项做准备，，下一次，也就是i+1项，dp1就是dp0了，=> 可以简化为一个变量》？
    				} // 简化代码： dp[i] = nums[i]+Math.max(dp[i-1],0); 
    				
    				max = Math.max(dp1, max);// 比较此次最大
    			}
    			
    			return max;
    		}
    
    		
    		 // 进一步简化
    		 // 如何理解？只考虑前一项情况就行，因为此时的项在下次判断时就变成了前一项
    		
             public int maxSubArray3(int []nums) { 
    			
    			int len = nums.length;
    // int[] dp = new int[len];
    			int dp0 = nums[0];// 定义初始条件,dp0为i-1项，dp1为当前项
    			int max = dp0;// 刚开始最大只能为第一个数
    			for(int i =1;i<len;i++) {  // 开始进行从i到len的情况测试，如果需要记录0-n之间具体情况，可进行打表
    				if(dp0<0) {  // 前i-1+1（数组从0开始）项最大值
    					// 小于0，只会越加越少，因此进行状态转移，将序列起点移动到i
    					dp0 = nums[i];
    				}else { 
    					dp0 = dp0+nums[i];// 否则进行累计
    					//dp0= dp1;//为下一项做准备，，下一次，也就是i+1项，dp1就是dp0了，=> 可以简化为一个变量》？
    				} // 简化代码： dp[i] = nums[i]+Math.max(dp[i-1],0); 
    				
    				max = Math.max(dp0, max);// 比较此次最大
    			}
    			
    			return max;
    		}
    }

3.打劫家舍  
题目：

> 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。  
> 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

略微不一样：  
考虑状态时：就想该处是偷还是不偷，考虑的是前一项和两项。

package dp;
    
    /** * * @author LYF * 问题描述： * [1,2,..] 数组表该家的金额，不能相邻的偷 * * 1.确定状态，，偷第i 家的最大利益 dp[i] * 2.确定状态转移 如果i家偷了，就为dp[i-2] 前两家的dp+该家的金额，没有偷就是前一家的最大利益dp[i-1] * 3.边界dp[0] ,dp[1] * 4.结果 * * => 思考：递推？？ * 另：暴力解决 * */
    public class Stole { 
    	// 100%,30多
    	 public int rob(int[] nums) { 
             
    		  int len = nums.length;
    	         if(len==1)
    	         return nums[0];
    
    			 int[] dp = new int[len];
    			 
    			 dp[0] = nums[0]; //第一项只能是自己
    			// dp[1] = nums[1];
    	      dp[1]= Math.max(nums[0],nums[1]);// dp[0]= // 第二项最大可以进行选择选第二项还是第一项
    			 
    			 int max = Math.max(dp[0], dp[1]);
    			 
    			 for(int i=2;i<len;i++) { 
    				 dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]); // 比较此时偷与不偷谁更大
    				 max = Math.max(max, dp[i]);// 比较此时是否更大
    			 }
    			 
    			 
    			 return max;
    	}
    	 
    	 
    	 //100%,50%
    	 
    public int rob2(int[] nums) { 
             
    		 int len = nums.length;
    
    		 // 内存优化
    		 int dp0,dp1;// 前2,1项
    		 
    		  dp0 = nums[0]; //第一项只能是自己
    	      dp1= Math.max(nums[0],nums[1]);// dp[0]= // 第二项最大可以进行选择选第二项还是第一项
    			 
    		 int max = dp1;// 肯定为dp1
    		 int temp =0;
    		 for(int i=2;i<len;i++) { 
    			// dp0= dp1;//前1项变为前2项；
    			 temp = dp1;
    			 // 下一次的前一项即i为前一项和前两项＋该i处的金额最大值
    			 dp1 = Math.max(dp1, dp0+nums[i]); // 比较此时偷与不偷谁更大
    			 // 下一次的前两项即为本次的前一项，由于dp1会改变，所以使用temp进行临时存储。
    			 dp0 = temp;
    			 // dp1为当前项最大利益，下一次前一项
    			 max = Math.max(max, dp1);// 比较此时是否更大
    		 }
    		 return max;
    	}
    }

四、总结

> 确定状态：根据该处的选择情况来确定（购买股票可以有两次选择，一个选择买入和卖出，因此需要设dp\[\]\[\]，而最长子序列，只用考虑该处是否重新开始以及小偷问题只需要考虑是否在该处偷即可，所以设立dp\[\]即可）  
> 确定状态转移：使用具体的值却推敲i与前项的关系

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/cdd9aacdc488473489975be243cf2b4d.png