萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

动态规划算法

发表于 2020-10-15 | 分类于 算法学习日记 | 0 | 阅读次数 424

简介

动态规划(Dynamic Programming,DP)可以将一个复杂的问题分解成若干个容易解决的子问题,再从这些子问题中求得到原问题的解。



动态规划题目特点

计算数值

  1. 有多少种方法走到哪里
  2. 有几种方法求出a个数使得和是sum

求最值

  1. 从右上角到右下角的最大数字
  2. 最长子序列长度

存在性判断

  1. 取石头游戏,先手必胜游戏
  2. 能否从n个数字中挑出m个数使得和是k


动态规划求解的四个组成部分

确定状态

  1. 研究最优策略的最后一步
  2. 转化为子问题

转移方程

  • 根据问题定义直接算出方程

初始条件和边界情况

  • 细节问题考虑周全

计算顺序

  • 利用之前的计算结果


例题


1.换硬币

题目描述

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回-1。

注意:你可以假设每种硬币均有无数个
总金额不会超过10000
硬币的种类数不会超过500, 每种硬币的面额不会超过100

样例
  1. 样例1
    输入:
    [1, 2, 5]
    11
    输出: 3
    解释: 11 = 5 + 5 + 1

  2. 样例2
    输入:
    [2]
    3
    输出: -1

题解
class Solution001{
	
	int coinChange(int [] coin, int M) {  // 输入coin为硬币面值数组,M为总金额
		
		int [] dp = new int[M + 1];  // 定义一个状态数组0..M
		
		dp[0] = 0;  // 初始化:组成0块钱需要0块硬币
		
		for (int i = 1; i <= M; i++) {  //遍历1..M,同时计算凑i块钱需要多少硬币
			
			dp[i] = Integer.MAX_VALUE;  // 初始化dp[i]为无穷大,方便后续比较大小
			
			for (int j = 0; j < coin.length; j++) {  // 遍历每种硬币凑i块钱使用的枚数最少
				if(i-coin[j] >= 0 && dp[i-coin[j]] != Integer.MAX_VALUE) {  // 下标需要大于等于0,无穷大需要舍去
					dp[i] = Integer.min(dp[i-coin[j]] + 1, dp[i]);  // 凑i块钱的方法数量是凑i-j块钱的方法数量+1,取最小值
				}
			}
			
			if(dp[M] == Integer.MAX_VALUE) {  // 应题目要求改成-1
				dp[M] = -1;
			}			
		}		
		return dp[M];  // 返回结果
	}
}
领扣第669题

2.不同的路径

题目描述

有一个机器人的位于一个m×n个网格左上角。
机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。
问有多少条不同的路径?

注意:n和m均不超过100
且答案保证在32位整数可表示范围内。

样例
  1. 样例1
    Input: n = 1, m = 3
    Output: 1
    Explanation: Only one path to target position.
  2. 样例2
    Input: n = 3, m = 3
    Output: 6
    Explanation:
    D : Down
    R : Right
    1. DDRR
    2. DRDR
    3. DRRD
    4. RRDD
    5. RDRD
    6. RDDR
题解
class Solution002{
	
	int robotWalking(int i, int j){
		
		int dp[][] = new int[i][j];  // 初始化方阵
		
		for (int a = 0; a < i; a++) {  // a行
			for (int b = 0; b < j; b++) {  // b列
				if(a == 0 || b == 0) {  
					dp[a][b] = 1;  // dp[0][b] = 1 , dp[a][0] = 1 ,左边和上边均赋值为1
				} else {
					dp[a][b] = dp[a][b - 1] + dp[a - 1][b];  // 到a行b列的方法数为dp[a][b-1]加上dp[a-1][b],即左边加上边。
				}
			}
		}
		return dp[i-1][j-1];  //返回答案
	}
}
领扣第114题

3.跳跃游戏

题目描述

给出一个非负整数数组,你最初定位在数组的第一个位置。   
数组中的每个元素代表你在那个位置可以跳跃的最大长度。    
判断你是否能到达数组的最后一个位置。

注意:数组A的长度不超过5000,每个元素的大小不超过5000

样例
  1. 样例1
    输入 : [2,3,1,1,4]
    输出 : true
  2. 样例2
    输入 : [3,2,1,0,4]
    输出 : false
题解
class Solution003{
	
	public boolean canJump(int a[]) {
		
		int n = a.length;  // 获取石头个数
		
		boolean[] dp = new boolean[n];  // 定义长度为n的布尔数组
		
		dp[0] = true;  // 初始化第一个为true
		
		for (int i = 1; i < n; i++) {  // 遍历1..n
			
			dp[i] = false;  // 先将当前状态设置成false
			
			for (int j = 0; j < i; j++) {  // 枚举0..i-1
				if(dp[j] && a[j] + j >= i) {  // 是否能到达第j块石头? 从第j块石头是否能跳到第i块石头?
					dp[i] = true;  // 满足条件设置成true
					break;  // 跳出循环
				}
			}
		}
		return dp[n - 1];  // 返回结果
	}
}
领扣第116题


  • 本笔记记录于此课程
# 算法 # 程序设计 # 动态规划
CentOS添加用户并赋予sudo权限
CentOS防火墙相关设置
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

83 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持