发表于 | 分类于 | 0 | 阅读次数 464

简介

动态规划（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题