初识动态规划（dynamic programming）

ゝ一纸荒年。 2022-02-02 11:01 303阅读 0赞

**动态规划（dynamic programming）**  
动态规划思想：其思想就是化整为零，减少重复的思想。  
复杂的原问题分化成更细小的子问题，解决子问题同时将子问题的解保存，使得相同的子问题只用求解一次，并且该解为下一个子问题提供基础，使下个子问题能快速进一步求解。  
小栗子：  
问：1+1+1+1+1=？  
答：等于5  
再问：那么 1+ 1+1+1+1+1=？  
答：1+5 =6（快速）  
（5是原来计算过的数据我们记录下来，后面只用在这个基础上+1就可以快速得出答案！）  
与递归法类似，比递归多了存储子问题的解的思想，减少了重复计算，时间空间复杂度由O（n^2）→O（n）  
**两种方法：**  
1、自顶而下（备忘录法）  
2、自下而上  
**方法说明：**

public static int f(int n,int [] bak/*数组集合*/) {//将计算过的数据存储到数组中（备忘录法）
    			 if(n==0||n==1) {
    			 return 1;
    		 }
    		 if(bak[n-1]!=-1) { //把数组初始化为 -1 如果不是则这个值我们储存过
    			 return bak[n];//返回该值
    		 }
    		 int result= f(n-1,bak)+f(n-2,bak);
    		 bak[n]=result;//记录下没储存但是计算过的元素  存起来~ 
    		 return result;
    	}

public static int f(int n) {//自下而上
    		 if(n==0||n==1) {
    		 return 1;
    	 }
    	 int result =0;
    	 int r1 = 1;
    	 int r2 = 1;
    	 for(int i = 2; i<=n;i++) { 
    		 result =r1+r2;	
    		 r1= r2;
    		 r2 =result;
    	 }
    	 return result;
    }

核心关键：递归，备忘（存储）  
这两种方法都用到递归，先将原问题细化，逐步解决子问题，存储子问题的解，为下个子问题的求解做基础，进而得到原问题的最优解。