java动态规划算法_南风知易✓✓✓的博客-程序员宅基地

java 动态规划算法

斐波那契数列

暴力解法

class Solution {
    
    //暴力递归解法
    public int fib(int n) {
    
        //base case 
        if(n==0||n==1) return n;
        return  fib(n-1)+fib(n-2);
    }
}

递归算法的时间复杂度=递归的次数x递归函数本身的时间复杂度

带备忘录的递归算法

class Solution {
    
    //带备忘录的递归算法
    public int fib(int n) {
    
        //备忘录全部初始化为0
        int [] memo=new int [n+1];
        //进行备忘录的递归
        return helper(memo,n);

    }
    private int helper(int []memo,int n){
    
        //base case
        if(n==0||n==1){
    
            return n;
        }
        //已经记录过就不用在计算了
        if(memo[n]!=0){
    
            return memo[n];
        }
        memo[n]=(helper(memo,n-1)+helper(memo,n-2))%1000000007;
        return memo[n];
    }
}


自底向上的dp数组迭代解法

class Solution {
    
    //自底向上的递归数组迭代dp法
    public int fib(int n) {
    
        if(n==0||n==1) return n;

        int []dp =new int [n+1];
        //base case
        dp[0]=0;dp[1]=1;
        //状态转移
        for(int i=2;i<=n;i++){
    
            dp[i]=(dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n];
    }
}

优化空间复杂度

class Solution {
    
    //优化空间复杂度
    public int fib(int n) {
    
        //base case
        if(n==0||n==1) return n;
        int pre=0,curr=1;
        int sum;
        for(int i=2;i<=n;i++){
    
            sum=(pre+curr)%1000000007;
            pre=curr;
            curr=sum;
        }
        return curr;

        
        
    }
}

零钱兑换问题

在这里插入图片描述

暴力递归算法

class Solution {
    
    //暴力递归解法


    //状态:目标金额amount
    //选择:coins数组中列出的所有硬币面额
    //函数的定义:凑出总金额amount,至少需要coinChage(coins,amount)枚硬币
    //base case:amount<0时不可能凑出,amount==0时需要0枚硬币
    public int coinChange(int[] coins, int amount) {
    
        //base case
        if(amount==0) return 0;
        if(amount<0) return -1;

        int res=Integer.Max_VALUE;
        for(int coin: coins){
    
            //计算子问题的结果
            int subRes=coinChange(coins,amount-coin);
            if(subRes==-1) continue;
            //在子问题中选择最优解,然后加1
            res=Math.min(res,subRes+1);
        }
        return res==Integer.Max_VALUE?-1:res;


    }
}



自顶向下递归–备忘录解法

class Solution {
    
    //备忘录

    //状态:目标金额amount
    //选择:coins数组中列出的所有硬币面额
    //函数的定义:凑出总金额amount,至少需要coinChage(coins,amount)枚硬币
    //base case:amount<0时不可能凑出,amount==0时需要0枚硬币

    int []memo;
    public int coinChange(int[] coins, int amount) {
    
        memo=new int [amount+1];
        //memo数组全部初始化为特殊值
        Arrays.fill(memo,-666);
        return dp(coins ,amount);

    }
    private int dp(int [] coins,int amount){
    
        //base case
        if(amount==0) return 0;
        if(amount<0) return -1;

        //查备忘录,防止重复计算
        if(memo[amount]!=-666){
    
            return memo[amount];
        }
        int res=Integer.MAX_VALUE;
        for(int coin:coins){
    
            //计算子问题的结果
            int subRes=dp(coins,amount-coin);
            if(subRes==-1)  continue;
            res=Math.min(res,subRes+1);
        }
        //把计算结果存入备忘录中
        memo[amount]=(res==Integer.MAX_VALUE?-1:res);
        return memo[amount];
    }
}

自底向上的迭代解法

class Solution {
    
    //自底向上的迭代解法
    public int coinChange(int[] coins, int amount) {
    
        int []dp=new int [amount+1];
        //dp数组全部初始化为特殊值
        Arrays.fill(dp,amount+1);

        //base case
        dp[0]=0;
        //外层for循环遍历所有状态的取值
        for(int i=0;i<dp.length;i++){
    
            for(int coin : coins){
    
                //子问题无解跳过
                if(i-coin<0) continue;
                //状态转移
                dp[i]=Math.min(dp[i],1+dp[i-coin]);
            }
        }
        //
        return (dp[amount]==amount+1)?-1:dp[amount];


    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/tianynnb/article/details/118340003

智能推荐

python获取用户图片文件夹路径_NairoJ的博客-程序员宅基地

要获取用户的图片文件夹目录,发现这些文件夹路径是存储在注册表中的这个路径之下HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\User Shell Folders 那也就用_winreg模块读取这个值就好了import _winkeykeys = _winreg.OpenKey(_winreg.HK...

Ubuntu 18.04安装ROS Melodic解决 sudo rosdep init 和 rosdep update失败的方法_浪子陪都的博客-程序员宅基地

Ubuntu 18.04安装ROS Melodic解决 sudo rosdep init 和 rosdep update失败的方法文章目录Ubuntu 18.04安装ROS Melodic解决 sudo rosdep init 和 rosdep update失败的方法前言1.打开软件和更新更换国内的源(这里选择清华源)2、打开终端(AlT+T),设置软件源,输入下列代码。3.设置密钥4、更新一下5、安装ros melodic完整版6、安装右键管理员权限(这里要安装)7、sudo rosdep init失

web网站开发基础_aevmb80648的博客-程序员宅基地

web网站开发基础web网站简单定义互联网基础原理简介君子与小人并存的互联网网站内容开发一个web项目需要经历哪些流程如何让你的网站能够让别人访问到一、web网站简单定义  web(World Wide Web)即全球广域网,也称为万维网,它是一种基于超文本和HTTP的、全球性的、动态交互的、跨平台的分布式图形信息系统。是建立在...

opencv反色图片(黑白互换)_sichuanwww的博客-程序员宅基地_opencv 黑白反色

IplImage *pImg = ::cvLoadImage("Ex.bmp");int nWidth = pImg->width;int nHeight = pImg->height;int nChannels = pImg->nChannels;int nStep = pImg->widthStep; for (i

【庄碰辉】感谢曾经的时光_豆舞咖啡的博客-程序员宅基地

感谢曾经的时光,无论是失去还是离别,要小心你的思想,因为它不久就成为你的行动,小心你的行动,因为它不久就成为你的习惯,小心你的习惯,因为它不久就成为你的品格。很多人,很多时候,常常被眼下的诸多不顺而打败,气馁于近处的磨难,殊不知年华如翻阅一本厚厚的定码书,看过去的越厚重,越沉稳,未翻阅的,在一天天熟悉。【豆舞咖啡】...

Java中PDF操作类库iText介绍_zhigangsun的博客-程序员宅基地

iText是一个非常著名的能够快速产生PDF文件的Java类库。支持文本,表格,图形的操作,可以方便的跟 Servlet 进行结合。授权协议: AGPLv3开发语言: Java操作系统: 跨平台 软件主页: http://itextpdf.com/文档地址: http://itextpdf.com/examples/index.php下载地址: http://sourc

随便推点

CalemEAM 添加新模块列表_Mast_God的博客-程序员宅基地

1.新建数据表此处省略2.添加表配置打开 eam\client\launchpad\resource\Metadata.js.gz(默认gz,修改调试后为min)表jsonCalemMetadata[表名]=[ "table_name":表名, "module":模块名/modCalemXXX , "cache_type": 缓存类型(database/dropdown/memory), "primary_key": 表主键, "lookup_mapping": { "fie

ArcSDE连接数限制问题_GADFLYGIS的博客-程序员宅基地

<br />ArcSDE最大连接数问题详解(转)<br />我们大体都知道ArcSDE的连接数有 48 的限制,很多人也知道这个参数可以修改,并且每种操作系统能支持的最大连接数是不同的。<br />如果应用报错:超出系统最大连接数 该如何处理?<br />两种解决办法:<br />第一,首先确定是否一定需要增加这个最大连接数。<br />在我们平常的应用中, 特别是给多用户的实施过程中。 有时会出现图形库莫名的连接不上, 如果用ARCMAP或ARCCATALOG连接的时候还会提示错误信息 “Failed t

查看docker镜像的运行命令_普通网友的博客-程序员宅基地_docker查询镜像命令

1.查看是否安装了pippip --versionpip查看1.1安装pipwget https://bootstrap.pypa.io/get-pip.pypython get-pip.py2.使用pip安装runlike服务sudo pip install runlike3.使用runlike查看docker镜像运行命令runlike -p redis(镜像名称)(备注:镜像名称获取)docker ps -a...

maven 改变java版本,在maven更新后,Java版本自动更改为java 1.5_红丝带学校郭小平的博客-程序员宅基地

I am using eclipse as IDE. When I right click on the project and then click maven update my java version change to 1.5. Here is what I did so far, I followed all the steps listed hereI changed "Java b...

S5P6818工控主板 ARM Cortex-A53架构_miaiz的博客-程序员宅基地

产品简介Gbox6818卡片电脑尺寸,差不多只是G6818开发板的三分之一,但它的功能相对于G6818开发板是有过之而无不及,几乎包括了G6818开发板所有外设功能,而且还板载VGA,USB WIFI/BT二合一模块,等; 软件上,Gbox6818和G6818开发板几乎完全兼容,无需做过多修改。 硬件上,Gbox4418和Gbox6818完全兼容,只需更换CPU,即可将A9四核升级到A53八核...

JAVA面试 —————— 计算机网络篇_*吴聪聪*的博客-程序员宅基地_java面试计算机网络

JAVA实习面试 —————— 计算机网络篇1、OSI 七层结构、TCP/IP四层结构、五层协议结构OSI七层:物理层、数据链路层、网络层、传输层、会话层、表示层、应用层TCP/IP 四层:网络接口层、网际层、运输层、应用层五层协议:物理层、数据链路层、网络层、运输层、应用层注意:按照从下到上的顺序。OSI七层参考模型,每一层的作用:对应的层作用对应的网络协议/硬件物理层提供数据传输的硬件保证,网卡接口,传输介质中继器、集线器、网关数据链路层进行数据交