简介
动态规划(Dynamic Programming,DP)可以将一个复杂的问题分解成若干个容易解决的子问题,再从这些子问题中求得到原问题的解。
动态规划题目特点
计算数值
- 有多少种方法走到哪里
- 有几种方法求出a个数使得和是sum
求最值
- 从右上角到右下角的最大数字
- 最长子序列长度
存在性判断
- 取石头游戏,先手必胜游戏
- 能否从n个数字中挑出m个数使得和是k
动态规划求解的四个组成部分
确定状态
- 研究最优策略的最后一步
- 转化为子问题
转移方程
- 根据问题定义直接算出方程
初始条件和边界情况
- 细节问题考虑周全
计算顺序
- 利用之前的计算结果
例题
1.换硬币
题目描述
给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回-1。
注意:你可以假设每种硬币均有无数个
总金额不会超过10000
硬币的种类数不会超过500, 每种硬币的面额不会超过100
样例
-
样例1
输入:
[1, 2, 5]
11
输出: 3
解释: 11 = 5 + 5 + 1 -
样例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]; // 返回结果
}
}
2.不同的路径
题目描述
有一个机器人的位于一个m×n个网格左上角。
机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。
问有多少条不同的路径?
注意:n和m均不超过100
且答案保证在32位整数可表示范围内。
样例
- 样例1
Input: n = 1, m = 3
Output: 1
Explanation: Only one path to target position. - 样例2
Input: n = 3, m = 3
Output: 6
Explanation:
D : Down
R : Right- DDRR
- DRDR
- DRRD
- RRDD
- RDRD
- 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]; //返回答案
}
}
3.跳跃游戏
题目描述
给出一个非负整数数组,你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。
注意:数组A的长度不超过5000,每个元素的大小不超过5000
样例
- 样例1
输入 : [2,3,1,1,4]
输出 : true - 样例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]; // 返回结果
}
}
- 本笔记记录于此课程