leetCode 322. 零钱兑换

标签: dp

在这里插入图片描述

class Solution {
    // dp[i] = dp[i-1]+dp[i-2] ?????  可以使用宽搜的方式来处理最短路径问题
    // dp[i] = min(dp[n-1],dp[n-2],...,dp[1])  k in [1,2,5]
    //思路分析: 有多条路径可以走 (使用自底向上的动态规划)
    public int coinChange(int[] path, int amount) {
        int[][]dp = new int[amount+1][path.length+1];

        for(int amt=1;amt<dp.length;++amt)
        {
            for(int j=0;j<dp[0].length;++j)
            {
                //if(i==0) continue;
                dp[amt][j] = amount+1;
            }
        }



     
        for(int i=1;i<=amount;++i)
        {
            for(int j=1;j<=path.length;++j)
            {
                if(i>=path[j-1])
                {
                    dp[i][j]= Math.min( dp[i][j-1] , dp[ i-path[j-1] ][j] + 1);
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }

        return dp[amount][path.length] >amount? -1:dp[amount][path.length];
    }
}

在这里插入图片描述在这里插入图片描述我们来看一下这个题的递归树,根据递归树写出状态转移方程


dp[i][j] = min(dp[i][j-1],dp[i-coin[j]][j]+1)
// i表示 有 i块钱
// j表示 coins[j] 对应的索引
// dp 表示这个递归树求的最短的路径

压缩一下空间

class Solution {
    // dp[i] = dp[i-1]+dp[i-2] ?????  可以使用宽搜的方式来处理最短路径问题
    // dp[i] = min(dp[n-1],dp[n-2],...,dp[1])  k in [1,2,5]
    //思路分析: 有多条路径可以走 (使用自底向上的动态规划) dp[i]=min(dp[i],dp[i-coin]+1)
    public int coinChange(int[] path, int amount) {
        int[] dp = new int[amount+1] ;

        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for(int i=1;i<dp.length;++i)
        {
            for(int j=0;j<path.length;++j)
            {
                if(i>=path[j])
                {
                    dp[i] = Math.min(dp[i],dp[i-path[j]]+1);//计算步数
                }
            }
        }
        return dp[amount]>amount?-1:dp[amount]; 

    }
}

当然,既然可以画出一颗递归树,那么就可以求这颗递归树的最短路径,这个问题就转化为了最短路径问题
使用bfs

class Solution {
    // dp[i] = dp[i-1]+dp[i-2] ?????  可以使用宽搜的方式来处理最短路径问题
    // dp[i] = min(dp[n-1],dp[n-2],...,dp[1])  k in [1,2,5]
    //思路分析: 有多条路径可以走 (使用自底向上的动态规划) dp[i]=min(dp[i],dp[i-coin]+1)
    public int coinChange(int[] path, int amount) {
        if(amount==0) return 0;

        Queue<Integer> q = new LinkedList<>();
        q.offer(amount);
        int level=0;
        boolean[] visited = new boolean[amount+1];
        visited[amount]=true;
        while(!q.isEmpty())
        {
            ++level;
            int len = q.size();
            for(int t=0;t<len;++t)
            {
                Integer node = q.poll();
                for(int p:path)
                {
                    if(node>=p)
                    {
                        int nextNode = node-p;
                        
                        if(!visited[nextNode])
                        {
                            q.offer(nextNode);
                            visited[nextNode]=true;
                            if(nextNode==0) return level;
                        }

                    }
                }
            }
        }
        return -1;
       

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

智能推荐

android问题记录

Error: Cannot fit requested classes in a single dex file (# methods: 80441 > 65536) 解决办法: gradle文件的defaultConfig默认配置里面增加...

ROS机器人Diego 1# 利用人工智能 风格迁移技术拍摄不同画风的视频

风格迁移,就是将一种图片的风格迁移到其他图片上,改变其他图片的风格,很好玩的一个人工自能模型,github上已经有很多实现的方法,本文参考https://github.com/hzy46/fast-neural-style-tensorflow 的算法,利用Diego1#的平台实现实时视频的风格转换,先上两张图看效果: 是不是很酷呢,其实实现方法和上篇博文中的原理是一样的,只是把人工智能的算法包装...

数据分析学习总结笔记17:文本分析入门案例实战

文章目录 1 数据准备 2 分词 3 统计词频 4 词云 5 提取特征 6 用sklearn进行训练 1 数据准备 数据样例如下, 数据总量为7.7万+: 本节通过一个实战的例子来展示文本分析的最简单流程。首先设定因变量为原始数据中的"评分"。自变量是"评价内容",这里根据评价内容提取TF-IDF特征。之后,通过评价内容的特征建模预测下整体评分。 以上只是最...

LeetCode 150. 逆波兰表达式求值

题目描述 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。 换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1: 输入:[“2”, “1”, “+”, “3&r...

并查集原理及应用

并查集 树形的数据结构,每个集合有其代表节点,代表节点相同的元素属于同一集合。 find:通过查找节点的代表节点,判断节点所属集合。 union:合并两集合,小集合合并到大集合,使用大集合的代表节点。 在find的递归过程中,让路过节点的父节点直接赋值为代表节点,节省下次查找时间,如图所示。 计算岛的个数 遍历二维数组,遇到1时就将所相连的1都改为2,看看遇到多少次1,就是岛的数量。改数时使用回溯...

猜你喜欢

linux nutch1.0安装配置

1,下载nutch1.0 下载地址:http://archive.apache.org/dist/nutch/,下载这个文件nutch-1.0.tar.gz   2,上传到服务器 上传位置:/home/www/,解压nutch-1.0.tar.gz #tar -xvf nutch-1.0.tar.gz 重命名 #mv nutch-1.0 nutch   3,修改配置文...

如何搭建自己的博客?附加美化

如何搭建自己的blog?附加美化 前言: 之前在腾讯云以学生优惠租了一年的服务器,还买了一年的域名,忽然觉得不能闲置着域名,所以搭建了个博客,过程也遇到了很多的问题,望在此阐述,予以他人帮助,祝好~ 准备工作:使用Xshell连接上Linux服务器,我的是centos系统,方便进行操作。使用Xftp连接上Linux服务器,方便传输文件。 安装apache服务器:yum install httpd ...

rabbitmq五种模式详解(含实现代码)

1.简单模式 当生产端发送消息到交换机,交换机根据消息属性发送到队列,消费者监听绑定队列实现消息的接收和消费逻辑编写.简单模式下,强调的一个队列queue只被一个消费者监听消费. 1.1 结构   生产者:生成消息,发送到交换机 交换机:根据消息属性,将消息发送给队列 消费者:监听这个队列,发现消息后,获取消息执行消费逻辑 1.2应用场景 常见的应用场景就是一发,一接的结构 例如: 手机...

AndroidStudio 常用配置

1. 设置主题&左侧导航栏字体 AndroidStudio->Preferences(下同) 2. 设置字体大小 3. 取消竖线 间距设置大些 4. 控制台字体大小 5. 修改LogCat颜色 LogCat 色值 Verbose BBBBBB Debug 48BB31 Info 0070BB Warn BBBB23 Error FF0006 Assert 8F0005 5. 修改变量...

Kafka Producer

1.Producer简介 kafakclients链接 2.构造Producer 2.1简单构造 1.构建配置文件 首先第一步是进行用户鉴权的操作(如果Kafka集群需要的话) 然后需要配置的三个主要参数 broker的地址 key、value的序列化 2.构建生产者发送消息 首先我们应该杜绝 fire and forget的操作这样可能会导致消息丢失。 同步发送 这样发送通过对异常的处理可以消息...