大家好，我是耀星🌟，欢迎来到动态规划频道📡，如何你是一枚新手的话，建议大家能够先学习🔍动态规划入门篇
目录
⌛动态规划题目特点
👇Example1 （换硬币）
👇Example2 （跳跃游戏）
👇Example 3 （解密方法）
👇Example 4（最长升序子串）
👇Example 5（调手表）
🚖坐标型动态规划总结
⌛动态规划题目特点
1.计数
-有多少种方式走到终点
-有多少种方式选出k个数的和相同
...
2.求最大值最小值
-求路径的最大最小数字和
-最长上升子序列长度
...
3.求存在性
-取石子游戏，先手是否必胜
-能不能选出k个数和是sum
...
👇Example1 （换硬币）
你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多，假设买一本书需要27元，如何用最少的数量的硬币买到这本书，如果给定金额不能够拼出返回-1。
LintCode链接：换硬币
⚖1.确定状态
⏯最后一步：
最后一步我们可能选2元，选择5元，选择7元，如果告诉你拼出25元最少要5枚，拼出22元最少要5枚，拼出20元最少要四枚。那么你最后当然会选择7元作为最后一枚硬币，拼出27元。
🏔子问题：
如果最后一步是选择2元
dp[27] = dp[27-2]+1;//转化为求25元能够用最少硬币拼出
如果最后一步是选择5元
dp[27] = dp[27-5]+1;//转化为求22元能够用最少硬币拼出
如果最后一步是选择7元
dp[27] = dp[20] +1;//转化为求20元能够用最少硬币拼出
我门只是做了假设最后一步应该怎么走，那么具体怎么走才是最优的呢？
dp[27] = min{dp[20],dp[25],dp[22]}+1
⚛2.转移方程
🌎3.初始条件和边界情况
dp[0] = 0;//0元用0枚硬币拼出
如过i-k<0时，则不能够拼出我们想要的数，设不能拼出为+∞。
例如我们想拼出dp[3]
🔀 4.计算顺序
dp[0] dp[1] dp[2] dp[3]....dp[n]
说明：题目中并没有给定确定的硬币面值，但是我们同样可以通过推导得出dp[i]=min{dp[i-k1],dp[i-k2],dp[i-k3]...dp[i-kn]}+1 .
public class Solution {
public int coinChange(int[] coins, int amount) {
int m = coins.length;
if(m == 0 || amount == 0){
return 0;
}
int[] dp = new int[amount+1];
//初始化
dp[0] = 0;
for(int i=1; i<=amount; i++){
dp[i] = Integer.MAX_VALUE;
//有m个不同的硬币
for(int j=0; j<m; j++){
if(i >= coins[j] && dp[i-coins[j]] != Integer.MAX_VALUE){//处理边界情况
dp[i] = Math.min(dp[i-coins[j]]+1,dp[i]);//转移方程
}
}
}
//拼不出返回-1
if(dp[amount] == Integer.MAX_VALUE){
return -1;
}
return dp[amount];
}
}
📝小结
↘最值型动态规划
↘动态规划组成部分
-1.确定状态
最后一步(最后一步应该如何选择硬币k)
子问题(选择最少的硬币，子问题dp[i-coins[j]]
2.转移方程
dp[i] = Math.min{dp[i-2],dp[i-5],dp[i-7]}+1;
3.初始条件和边界情况
dp[0] = 0;
不能拼出i,dp[i] = Integer.MAX_VALUE;
👇Example2 （跳跃游戏）
给出一个非负整数数组，你最初定位在数组的第一个位置。数组中的每个元素代表你在那个位置可以跳跃的最大长度。判断你是否能到达数组的最后一个位置。
样例
输入：A=[2,3,1,1,4]
输出：true
LintCode链接：跳跃游戏
⚖1.确定状态
设定一个数组dp[i]表示是否能够跳到第i个位置，能够跳到为true，不能够跳到为false.
⏯最后一步：从数组的第一个位置开始跳，最后一步要求跳到第n-1块石头，设最后一步是从第i块石头跳到n-1
🏔子问题：是否能够跳跃到第i个位置
🍱原问题：是否能够跳到第n-1个位置
想要跳到n-1,第i个位置需要满足的条件有：
dp[i] == true
i+A[i] >= n-1//从第i个位置开始跳，i+A[i]能够跳到的最大位置>=n-1,那么就能跳到第n-1个位置
状态：dp[i]表示能否跳到第i个位置
⌛2.转移方程
用变量j向前枚举
☑3.初始条件和边界情况
起始位置为数组的第一个元素，所以第一个位置一定能够跳到
dp[0] = true
🔀4.计算顺序
dp[0] dp[1] dp[2] dp[3]...dp[n-1]
public class Solution {
public boolean canJump(int[] A) {
int n = A.length;
if(n == 0 || A==null){
return false;
}
boolean[] dp = new boolean[n];
dp[0] = true;
for(int i=1; i<n;i++){
dp[i] = false;
for(int j = i-1;j>=0;j--){
if(dp[j] == true && j+A[j] >= i){
dp[i] = true;
break;
}
}
}
return dp[n-1];
}
}👇Example 3 （解密方法）
解密方法：有一段数字序列，将该段数字序列解密成字符串，一共有多少种解密方法。
1-A 2-B 3-C... 26-Z
例如：
12：L或AB
LintCode链接：解密方法
⚖1.确定状态
⏯最后一步：最后一个字符可能由两位数组成，也有可能由一位数组成。
例如：128439516
将数字序列划分成若干段数字序列
6为最后一个数字，最后一步可以拼成一个F，16作为最后一个数字也可以可以解密为一个P，如果告诉你N-1个数可以拼出的N1种方案，N-2个数可以拼出N2种方案，那么你一定会计算N个数有多少种解密方法。
🐢子问题：求N-1和N-2个数字序列的解密方法
🍱原问题：求N个数字序列的解密方法
状态：前i个数字序列，有dp[i]种解密方法
⚛2.转移方程
☑3.初始条件和边界情况
初始条件：dp[0] = 1即空串有一种解密方式
边界情况：i == 1,只看最后一个数字
当最后一位是0时，可能由两位数字组成，若两位都为0或两位大于26则不能组成字符串，所以先默认dp[i] = 0，若不满足组成字符条件，则dp[i]就为0。
🔀4.计算顺序
dp[0] dp[1] dp[2] dp[3] ...dp[n]
public class Solution {
=
public int numDecodings(String s) {
char[] ss = s.toCharArray();
int n = ss.length;
if(n == 0){
return 0;
}
int[] dp = new int[n+1];
dp[0] = 1;
for(int i=1; i<=n; i++){
dp[i] = 0;先初始化为0，可能存在不能组成字符串的情况
//用一个字符作为结尾
int t1 = ss[i-1]-'0';
if(t1>0 && t1<=9){//若t == 0,自动选择后两位作为一个字符
dp[i]+=dp[i-1];
}
if(i>=2){
//取出倒数第二位
int t2 = (ss[i-2]-'0')*10+ss[i-1]-'0';
if(t2<=26 && t2>=10){//最后两位小于26并且大于等于10才能组成字符
dp[i]+=dp[i-2];
}
}
}
return dp[n];
}
}👇Example 4（最长升序子串）
给定一个整数数组（下标从 0 到 n-1， n 表示整个数组的规模），请找出该数组中的最长上升连续子序列。（最长上升连续子序列可以定义为从右到左或从左到右的序列。）
LintCode链接：最长升序子串
输入：[5, 4, 2, 1, 3]
输出：4
解释：
给定 [5, 4, 2, 1, 3]，其最长上升连续子序列（LICS）为 [5, 4, 2, 1]，返回 4。
⚖1.确定状态
通过最优策略选择出最长升序子串的长度
⏯最后一步 ：如果告诉你以A[i-1]为结尾的升序子串长度为为N1，如果A[i]>A[i-1]，那么以A[i]为结尾的升序子串长度为N1+1,如果A[i]<A[i-1]，那么以A[i]为结尾的升序子串长度为1。
🐢子问题：只要知道A[i-1]作为升序子串中最后一个元素的最长升序子串的长度。
🍱原问题：求A[i]前的最长升序子串的长度。
状态：使用dp[i]记录以A[i]元素为为结尾的升序子串中最后一个元素的长度。
例如：
⚛2.转移方程
☑3.初始条件和边界情况
初始条件：
dp[0] = 1
🔀4.计算顺序
dp[0] dp[1] dp[2] dp[3]...dp[n-1]
public class Solution {
//计算最长升序子列
public int MyLongstIncreasingContinuousSubsequence(int[] A){
int n = A.length;
if(n == 0 || A == null){
return 0;
}
int[] dp = new int[n];
//初始化
dp[0] = 1;
int max = 1;//记录最长子串
for(int i=1; i<n;i++){
dp[i] = 1;//若没有递增默认为1
if(A[i]>A[i-1]){
dp[i] = Math.max(1, dp[i-1]+1);
max = Math.max(dp[i],max);
}
}
return max;
}
public int longestIncreasingContinuousSubsequence(int[] A) {
int ret1 = MyLongstIncreasingContinuousSubsequence(A);
//倒置字符串，计算最长降序子串
int left = 0;
int right = A.length-1;
while(left < right){
int temp = A[left];
A[left] = A[right];
A[right] = temp;
left++;
right--;
}
int ret2 = MyLongstIncreasingContinuousSubsequence(A);
int result = Math.max(ret1, ret2);
return result;
}
}👇Example 5（调手表）
小明买了块高端大气上档次的电子手表，他正准备调时间呢。在 M78 星云，时间的计量单位和地球上不同，M78 星云的一个小时有 n分钟。大家都知道，手表只有一个按钮可以把当前的数加一。在调分钟的时候，如果当前显示的数是 0 ，那么按一下按钮就会变成 1，再按一次变成 2 。如果当前的数是 n - 1按一次后会变成 0。作为强迫症患者，小明一定要把手表的时间调对。如果手表上的时间比当前时间多 1，则要按 n - 1 次加一按钮才能调回正确时间。小明想，如果手表可以再添加一个按钮，表示把当前的数加 k 该多好啊......他想知道，如果有了这个+k 按钮，按照最优策略按键，从任意一个分钟数调到另外任意一个分钟数最多要按多少次。
注意，按 +k按钮时，如果加 k 后数字超过 n-1则会对 n 取模。
比如，n=10, k=6 的时候，假设当前时间是 0，连按 2 次 +k+k 按钮，则调为 2。
输入描述
一行两个整数 n, k（0 < k < n <10^5) (0<k<n≤10^5）意义如题。
输出描述
输出一行一个整数，表示按照最优策略按键，从一个时间调到另一个时间最多要按多少次。
OJ链接：调手表
📡1.确定状态
🌎最后一步：
最后一步要调到n-1的位置，可以从n-1-1 || n-1-k || (j*k)%n的位置调到n-1。
🐢子问题:
如果最优策略是从i-1~i
如果最优策略是从i-k~i
如果最优策略是(j*k)%n~i
转化为求调到时间i-1或i-k或(j*k)%n的最优策略
👉原问题：求调第到第n-1分钟的最优策略
🍉状态：dp[i]为调第i分钟，按表的最少次数。
✨2.转移方程
🚲3.初始条件及边界情况
初始条件:
dp[0] = 0
🔀4.计算顺序
dp[0] dp[1] dp[2] dp[3]...dp[n-1]
import java.util.Scanner;
import java.util.Arrays;
public class Solution {
public int MinNumberOfTime {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = scan.nextInt();
int[] dp = new int[n];
dp[0] = 0;初始化
for(int i=1;i<n;i++){
dp[i] = dp[i-1]+1;
if(i-k>=0 && k>1){
dp[i] = Math.min(dp[i-k]+1,dp[i]);
}
for(int j=2;j<dp[i];j++){//寻找可行的j
if((j*k)%n == i){
dp[i] = Math.min(dp[i],j);
break;
}
}
}
排序找到最大数
Arrays.sort(dp);
return dp[n-1]
}
}🚖坐标型动态规划总结
🎆给定输入为序列或者网格
🎈动态规划状态下标为序列下标i或者坐标(i,j)
--dp[i]表示以i个元素结尾的某种性质
--d[i][j]表示以坐标(i,j)为结尾的性质
💌初始化设置dp[0]或dp[0][0...n]的值
🛑二维空间优化：滚动数组节省空间
水平有限⏰，希望能够对大家有帮助。感谢大家的支持🙆！
相关文章
