动态规划从简单到入门

2019/7/22 16:05:56 人评论 次浏览 分类:学习教程

动态规划问题从简单到入门

在之前我们接触排序问题中,有一个特别好的思想被称为分治思想。分治思想的核心在与如何划分,怎样分治怎样大化小。由此延伸今天的问题 动态规划
一般来说动态规划更像是递归的做法,抽取问题的相同点划分问题整体,将所有的步骤分开

1.把原来的一个大问题分解成小步骤小问题
例如: 斐波那契数列在解决时我们很难一次性计算出最终解,但是我们可以分析出,最终解是由前一个解推理而来 所以问题转变为求上一个解,依次进行类推。

2.把所有的子问题只需要解决一次
例如:在斐波那契中每一个解 都是由前两个解得出 f(n) = f(n-1)+f(n-1),这对于每一个解都适用

3.储存子问题的解
例如:在斐波那契中我们所计算出来的解 在解决之后的解中都会用到并且不能改变
动态规划的切入点
状态的定义 状态方程的定义
产生动态规划的思路
1.定义状态
2.状态间的转移方程定义
3.状态初始化
4.返回结果

(1)斐波那契数列

题目不再描述,开始分析
1、定义状态 满足函数关系 f(i)
2、状态间转移方程定义 f(i) = f(i-1)+f(i-2)
3、初始值 f(1)=1 f(2)=1
4、返回结果 f(i)

public class Solution {
    public int Fibonacci(int n) {
        if(n<=0){
            return 0;
        }
        if(n==1||n==2){
            return 1;
        }
        int[] arr = new int[n+1];
        arr[0] = 0;
        arr[1] = 1;
        for(int i=2;i<=n;i++){
            arr[i] = arr[i-1]+arr[i-2];
        }
        return arr[n];
    }
}```
直观上看,与递归的方式解决问题相类似,这里采用将每一次结果存储在数组中,下一次所使用的还是数组中的数据,比较递归的方式,不存在函数调用深度过深栈溢出
开辟数组时,还是会浪费空间
```javascript
     if(n<=0){
            return 0;
        }
        if(n==1||n==2){
            return 1;
        }
        int f1 = 1;
        int f2 = 1;
        int ret = 0;
        for(int i=3;i<=n;i++){
            ret = f1+f2;
            f1 = f2;
            f2 = ret;
        }
        return ret;

(2)青蛙跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级台阶总共有多少种跳法。

1.状态 跳1 跳2 跳3。。。n阶跳法总数
F(n) 还剩多少阶跳法
2.状态推导方程
跳1 剩f(n-1)
跳2 剩f(n-2)
跳3 剩f(n-3)

跳n 剩f(n-n)
总的跳法 跳1+跳2+跳3。。。跳n
F(n) = f(n-1)+f(n-2)+f(n-3)…f(0)
数学推导
F(n) = 2f(n-1)
初始值
F(1) = 1;
F(2) = 2
f(1) = 2;
F(3) = 2f(2) = 22*f(1) = 4;

F(n) = 2^(n-1);

返回结果
F(n)

public class Solution {
    public int JumpFloorII(int target) {
        int[] arr = new int[target+1];
           arr[0] = 1;
        for(int i=1;i<=target;i++){
            arr[i] = 2*arr[i-1];
        }
        return arr[target-1];
    }
}

我们可以使用之前得出的动态规划模板找出动态方程求出结果
对代码进行优化

public class Solution {
    public int JumpFloorII(int target) {
        return (int)Math.pow((double)2,(double)target-1);
        /*
        int[] arr = new int[target+1];
           arr[0] = 1;
        for(int i=1;i<=target;i++){
            arr[i] = 2*arr[i-1];
        }
        return arr[target-1];
        */
    }
}

(3)最大连续子数组和

动态规划不但可以解决数字性的题目,也可解决抽象题目
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式 识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0
个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)
子状态
长度1 长度2 长度3 。。。长度n的组数组最大值
F(i) 以array[i]元素末尾子数组最大值
状态递推
F(i) = max(F(i-1)+array[i]),array[i])
通过比较加上末尾的子串值是否大于子串大于则相加
因为求最大值当F(i-1)+array[i]<0也要考虑
返回结果
Max(F(i))

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int sum = array[0];
        int maxtmp = array[0];
        for(int i=1;i<array.length;i++){
            sum = (sum>0)?sum+array[i]:array[i];
            /*
           if(sum<0){
               sum = array[i];
           }else{
               sum+=array[i];
           }*/
            
            maxtmp = (sum<maxtmp)?maxtmp:sum;
           /*
            if(sum>maxtmp){
                   maxtmp = sum;
               }*/
        }
        return maxtmp;
    }
}

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->