算法-中等-动态规划

迷南。 2022-11-18 01:41 84阅读 0赞

# 动态规划 #

## **理解** ##

记录上一次的状态，之后在现有的数据上进行操作，得到新的状态，从而避免操作过多过长的数据造成难以计算的情况。

### **举例理解** ###

9x8x6x2=864。虽然数据不多，但是脑子算还是得想想。这时候，我们再来计算9x8x6x2x2肯定是864x2会好计算点，而不是从新计算9x8x6x2x2。

## 方法 ##

### **①自顶向下的备忘录法** ###

public static int Fibonacci(int n)
    { 
            if(n<=0)
                return n;
            int []Memo=new int[n+1];        
            for(int i=0;i<=n;i++)
                Memo[i]=-1;
            return fib(n, Memo);
        }
        public static int fib(int n,int []Memo)
        { 
    
            if(Memo[n]!=-1)
                return Memo[n];
        //如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。 
            if(n<=2)
                Memo[n]=1;
    
            else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo);  
    
            return Memo[n];
        }

创建了一个n+1大小的数组来保存求出的斐波拉契数列中的每一个值，在递归的时候如果发现前面fib（n）的值计算出来了就不再计算，如果未计算出来，则计算出来后保存在Memo数组中，下次在调用fib（n）的时候就不会重新递归了。

### **②自底向上的动态规划** ###

public static int fib(int n)
    { 
            if(n<=0)
                return n;
            int []Memo=new int[n+1];
            Memo[0]=0;
            Memo[1]=1;
            for(int i=2;i<=n;i++)
            { 
                Memo[i]=Memo[i-1]+Memo[i-2];
            }       
            return Memo[n];
    }

备忘录法还是利用了递归，上面算法不管怎样，计算fib（6）的时候最后还是要计算出fib（1），fib（2），fib（3）……,那么何不先计算出fib（1），fib（2），fib（3）……,呢？这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。

## 例题 ##

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

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

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。  
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。