当前位置：移动技术网 > IT编程>开发语言>Java > 学习笔记——动态规划专题

学习笔记——动态规划专题

2020年07月15日 | 移动技术网IT编程 | 我要评论

动态规划的题目特点

计数型
有多少种方式走到右下脚
有多少种方法选出k个数的和是sum
求最大值最小值型
从左上角走到右下角路径的最大数字和
最长上升子序列长度
求存在性型
取石子游戏，先手是否必胜
能不能选出k个数使得和为sum
坐标型
最简单的动态规划类型
需要找到序列中某个/写子序列或网格中的某条路径
二维空间优化：可以用滚动数组优化节省空间
序列型
划分型

动态规划的总结

1、确定状态

研究最优策略的最后一步
化为子问题

2、转移方程

根据子问题定义直接得到

3、初始条件和边界条件

细心、考虑周全

4、计算顺序

利用之前的计算结果

例题解析及其代码

例题一：求最大值最小值型

题目：你有三种硬币，分别面值为2元，5元和7元，每种硬币都有足够多，买一本书需要27元，如何用最少的硬币组合？

递归解法：

int f(int X){
	if(X == 0) return 0;
	int res = MAX_VALUE;
	if(X >= 2){
		res = Math.min(f(X - 2) + 1, res);
	}
	if(X >= 5){
		res = Math.min(f(X - 5) + 1, res);
	}
	if(X >= 7){
		res = Math.min(f(X - 7) + 1, res);
	}
	return res;
}

递归解法存在的问题：做了很多的重复计算，效率低下。

动态规划解法：
我们按照动态规划的总结步骤来进行分析：

确定状态
– 最后一步：除掉最后一枚硬币a_k，前面的面值加起来是27 - a_k。
– 将原问题转化成了一个子问题：最少用多少枚硬币拼出27 - a_k。
转移方程
根据子问题的定义：f[X]=min{f[X-2]+1,f[X-5]+1,f[X-7]+1}
初始条件和边界条件
初始条件：f[0] = 0
若X<0，则f[X] = ∞
计算顺序
f[0],f[1],f[2]...

代码实现：

public class Solution {
    public int coinChange(int[] A, int M) {
        int[] f = new int[M + 1];
        int n = A.length;	//硬币的数量
        
        f[0] = 0;	//初始化
        int i, j;
        for (i = 1; i <= M; ++i) {
            f[i] = Integer.MAX_VALUE; 
            for (j = 0; j < n; ++j) {
                //边界条件
                if (i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE) {
                    f[i] = min(f[i],f[i - A[j]] + 1);
                }
            }
        }
        if(f[M] == Integer.MAX_VALUE)
            return -1;
        else return f[M];
    }
}

正确答案：7+5+5+5+5=27, 5枚硬币

例题二：计数型

题目：有一个机器人的位于一个 m × n 个网格左上角，机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角，问有多少条不同的路径？（n和m均不超过100 且答案保证在32位整数可表示范围内。）
在这里插入图片描述
动态规划解法：
我们依旧按照动态规划的总结步骤来进行分析：

确定状态
– 最后一步：无论机器人用何种方式到达右下角，总有最后挪动的一步。f[i][j]为机器人有多少种方式走到(i,j)。
– 子问题：前一步机器人一定是在(m-2,n-1)或者(m-1,n-2)，机器人有多少种方式从左上角走到(m-2,n-1)和(m-1,n-2)。
转移方程
根据子问题的定义：f[i][j]=f[i-1][j]+f[i][j-1]
初始条件和边界条件
初始条件：f[0][0] = 1，因为机器人只有一种方式到左上角
边界条件：i=0或者j=0，则前一步只能从一个方向（上或者左）过来，其中f[i][j]=1。
计算顺序
按行的方式来计算，f[0][0]=1
计算第0行：…
计算第1行：…
…
计算第m-1行：…

代码实现：

public class solution{
	public int uniquePaths(int m, int n) {
        // write your code here
        int[][] f = new int[m][n];
        int i,j;
        for(i=0;i<m;i++){
            for(j=0;j<n;j++)
            {
                //边界条件和边界条件
                if(i==0||j==0)
                {
                    f[i][j]=1;
                    continue;
                }
                f[i][j]=f[i-1][j]+f[i][j-1];
            }
        }
        return f[m-1][n-1];
}

样例：

Example 1:
Input: n = 1, m = 3
Output: 1	
Explanation: Only one path to target position.

Example 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

例题三：求存在性型

题目：有n块石头分别在x轴的0，1，…，n-1的位置，有一只青蛙在石头0，想跳到石头n-1。如果青蛙在第i块石头上，它最多可以向右跳距离a_i，问青蛙能否跳到石头n-1？
在这里插入图片描述
动态规划解法：
我们依旧按照动态规划的总结步骤来进行分析：

确定状态
– 最后一步：如果青蛙能跳到最后一块石头n-1，需要同时满足两个条件：青蛙可以跳到石头i，且最后一步不能超过最大跳跃距离：n-1-i<a~i~。
– 子问题：青蛙能不能跳到石头i
转移方程
根据子问题的定义：f[j] = OR~0<=i<j~ (f[i] AND i + a[i] >= j)
初始条件和边界条件
初始条件：f[0] = True，因为青蛙一开始就在石头0上
计算顺序
f[0],f[1],f[2]…f[n-1]`

代码实现：

public class Solution {
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    public boolean canJump(int[] A) {
        // write your code here
        int n = A.lenghth;
        boolean[] f = new boolean[n];
        
        //初始化
        f[0] = True;
        int i,j; 
        for(j = 1;j < n; j++)
        {
            f[j] = True;
            for(i = 0;i < j; i++)
            {
                if(f[i] && i + A[i] >= j)
                {
                    f[j] = True;
                    break;
                }
            }
        }
        return f[n-1];
    }
}

案例输入输出：
在这里插入图片描述

例题四：求最值型

题目：给定a[0],…,a[n-1]，找到最长的连续子序列i，i+1，i+2，…，j，使得a[i] * a[i+1] * ... * a[j]最大。

动态规划解法：
我们依旧按照动态规划的总结步骤来进行分析：

确定状态
– 最后一步：一定有最后一个元素a[j]，有两种情况：一、最优策略就是序列{a[j]}；二、连续子序列长度大于1，那么a[j]前一个元素肯定是a[j-1]
– 子问题：同时保存两个极值，求以a[j]结尾的连续子序列最大乘积和a[j]结尾的连续子序列最小乘积（考虑负数情况）
转移方程
两种情况：
一、f[j] =以a[j]结尾的最大乘积：f[j] = max{ a[j], max{a[j]*f[j-1], a[j]*g[j-1]}| j>0}
二、f[j] =以a[j]结尾的最小乘积：g[j] = min{ a[j], min{a[j]*f[j-1], a[j]*g[j-1]}| j>0}
初始条件和边界条件
初始条件：空
边界条件：情况2必须满足a[j]前面至少还有一个元素
计算顺序
f[0], g[0], f[1], g[1], f[2], g[2],…, f[n-1], g[n-1]

代码实现：

public class Solution {
    public int maxProduct(int[] nums) {
        // write your code here
        int n = A.length();
        if(n == 0)
            return 0
            
        int[] f = new int[n];
        int[] g = new int[n];
        int i;
        int res = Integer.MIN_VALUE;
        for(i = 0;i < n; i++){
            f[i] = A[i];
            if(i > 0){
                f[i] = Math.max(f[i], Math.max(A[i] * f[i-1], A[i] * g[i - 1]));
            }
            
            g[i] = A[i];
            if(i > 0){
                g[i] = Math.min(f[i], Math.min(A[i] * f[i-1], A[i] * g[i - 1]));
            }
        }
        res = Math.max(res, f[i]);
    }
}

案例输入输出： 在这里插入图片描述

例题五：坐标型

题目：不同的路径2。“不同的路径” 的跟进问题：现在考虑网格中有障碍物，那样将会有多少条不同的路径？

代码实现：

public class Solution {
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    public int uniquePathsWithObstacles(int[][] A ) {
        // write your code here'
        int m = A.length;
        if (m == 0) return 0;
        int n = A[0].length;
        if (n == 0) return 0;
        
        int[][] f = new int[m][n];
        int i,j;
        for(i = 0;i < m; i++)
        {
            for(j = 0;j < n; j++)
            {
                if(A[i][j] == 1){
                    f[i][j] = 0;
                    continue;
                }
                if(i==0 && j==0){
                    f[i][j] = 1;
                    continue;
                }
                f[i][j] = 0;
                if(i>0)
                {
                    f[i][j] += f[i-1][j];
                }
                if(j>0)
                {
                    f[i][j] += f[i][j-1];
                }
            }
        }
        return f[m-1][n-1];
    }
}

输入输出：

样例
Example 1:
	Input: [[0]]
	Output: 1

Example 2:
	Input:  [[0,0,0],[0,1,0],[0,0,0]]
	Output: 2
	
	Explanation:
	Only 2 different path.

例题六：序列型

题目：房屋染色。这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的费用。
在这里插入图片描述
代码实现：

public class Solution {
    /**
     * @param costs: n x 3 cost matrix
     * @return: An integer, the minimum cost to paint all houses
     */
    public int minCost(int[][] C ) {
        // write your code here
        int n=C.length;
        if(n == 0)  return 0;
        
        // 数列型
        int[][] f = new int[n + 1][3];
        f[0][0] = f[0][1] = f[0][2] = 0;
        int i,j,k;
        for(i = 1;i < n+1; i++){
            for(j = 0;j < 3; j++){
                f[i][j] = Integer.MAX_VALUE;
                //枚举倒数第二栋房子
                for(k = 0;k < 3; k++){
                    if(k != j){
                        f[i][j] = Math.min(f[i][j], f[i-1][k] + C[i-1][j]);
                    }
                }
            }
        }
        return Math.min(f[n][0],Math.min(f[n][1],f[n][2]));
    }
}

输入输出：

样例
样例 1:

输入: [[14,2,11],[11,14,5],[14,3,10]]
输出: 10
解释: 第一个屋子染蓝色，第二个染绿色，第三个染蓝色，最小花费：2 + 5 + 3 = 10.
样例 2:

输入: [[1,2,3],[1,4,6]]
输出: 3

例题七：划分型

题目：解码方法。有一个消息包含A-Z通过以下规则编码
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
现在给你一个加密过后的消息，问有几种解码的方式

代码实现：

public class Solution {
    /**
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    public int numDecodings(String ss) {
        // write your code here
        char[] s = ss.toCharArray();
        int n = s.length;
        if(n == 0)  return 0;
        
        int[] f = new int[n + 1];
        f[0] = 1;
        
        int i,j;
        for(i = 1;i <= n; i++){
            f[i] = 0;
            if(s[i - 1] > '0' && s[i - 1] < '9'){
                f[i] += f[i - 1];
            }
            
            if(i > 1){
                j = (s[i - 2] -'0') * 10 + (s[i - 1] -'0');
                if(j >= 10 && j<= 32){
                    f[i] += f[i - 2];
                }
            }
        }
        return f[n];
    }
}

输入输出：

样例
样例 1:

输入: "12"
输出: 2
解释: 它可以被解码为 AB (1 2) 或 L (12).
样例 2:

输入: "10"
输出: 1

例题八：序列型

题目：最长连续的单调子序列。首先，对于a[j]>al[i+1]>…>a[j]，可以将整个a序列倒过来，就变成求最长连续上升子序列了。所以，只需要考虑找到最长的a[i]<a[i+1]…<a[j]，可以从每个a[j]开始，一直向后延伸找到最长的连续上升序列。
代码实现：

public class Solution {
    public int LIS(int[]A, int n) {
         int i,j;
         int[] f =new int[n];
         int res = 0;
         
         for(i = 0;i < n; i++){
             f[i] = 1;
             if(i > 0 && A[i] > A[i - 1]){
                 f[i] = f[i - 1] + 1;
             }
             res = Math.max(res, f[i]);
         }
         return res;
    }
    public int longestIncreasingContinuousSubsequence(int[] A){
        int n=A.length;
        if(n == 0) return 0;
        
        int r1 = LIS(A, n);
        //reverse
        int i,j,t;
        while(i < j){
            t = A[i];
            A[i] = A[j];
            A[j] = t;
            ++i;
            --j;
        }
        
        int r2 = LIS(A, n);
        return r1 > r2 ? r1 : r2;
    }
 }

例题九：求最值型

题目：求最小路径。给定m行n列的网格，每个格子(i, j)里都一个非负数A[j]0]求一个从左上角(0, 0)到右下角的路径，每一步只能向下或者向右走一步使得路径上的格子里的数字之和最小，输出最小数字和。
在这里插入图片描述
代码实现：

public class Solution {
    /**
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    public int minPathSum(int[][] G) {
        // write your code here
        int m = G.length;
        int n = G[0].length;
        
        int[][] f = new int[m][n];
        int i,j;
        f[0][0] = G[0][0];
        for(i = 0;i < m; i++){
            for(j = 0;j < n; j++){
                if(i == 0 && j != 0){
                    f[i][j] = G[i][j] + f[i][j - 1];
                    continue;
                }
                if(j == 0 && i != 0) {
                    f[i][j] = G[i][j] + f[i-1][j];
                }
                if(i > 0 && j > 0){
                    f[i][j] = Math.min(f[i - 1][j] + G[i][j], f[i][j - 1] + G[i][j]);
                }
            }
        }
        return f[m - 1][n - 1];
    }
}

例题十：坐标型

题目：炸弹袭击。定一个二维矩阵, 每一个格子可能是一堵墙 W,或者一个敌人 E 或者空 0 (数字 ‘0’)，返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。由于墙比较坚固，所以墙不会被摧毁。（只能在’0’处放炸弹）

代码实现：

public class Solution {
    /**
     * @param grid: Given a 2D grid, each cell is either 'W', 'E' or '0'
     * @return: an integer, the maximum enemies you can kill using one bomb
     */
    public int maxKilledEnemies(char[][] G) {
        // write your code here
        // if(G.length == NULL || G[0].length == NULL)    
        // {
        //     return 0;
        // }
        int m = G.length;
        int n = G[0].length;
        
        int[][] f = new int[m][n];
        
        int[][] up = new int[m][n];
        int[][] down = new int[m][n];
        int[][] right = new int[m][n];
        int[][] left = new int[m][n];
        
        //初始化
        int i,j;
        for(i = 0;i < m; i++){
            for (j = 0;j < n; j++){
                up[i][j] = 0;
                if(G[i][j] == 'W'){
                    up[i][j] = 0;
                    continue;
                }
                if(G[i][j] == 'E'){
                     up[i][j] = 1;
                } 
                if(i > 0)
                {
                    up[i][j] += up[i - 1][j];
                }
            }
        }
        
        for(i = m - 1;i >= 0; i--){
            for (j = 0;j < n; j++){
                down[i][j] = 0;
                if(G[i][j] == 'W'){
                    down[i][j] = 0;
                    continue;
                }
                if(G[i][j] == 'E'){
                     down[i][j] = 1;
                } 
                if(i < m - 1)
                {
                    down[i][j] += down[i + 1][j];
                }
            }
        }
        
        for(j = 0;j < n; j++){
            for (i = 0;i < m; i++){
                right[i][j] = 0;
                if(G[i][j] == 'W'){
                    right[i][j] = 0;
                    continue;
                }
                if(G[i][j] == 'E'){
                     right[i][j] = 1;
                } 
                if(j > 0)
                {
                    right[i][j] += right[i][j - 1];
                }
            }
        }
        for(j = n - 1;j >= 0; j--){
            for (i = 0;i < m; i++){
                left[i][j] = 0;
                if(G[i][j] == 'W'){
                    left[i][j] = 0;
                    continue;
                }
                if(G[i][j] == 'E'){
                     left[i][j] = 1;
                } 
                if(j < n-1)
                {
                    left[i][j] += left[i][j + 1];
                }
            }
        }
        int res = 0;
        for(i = 0;i < m; i++){
            for(j = 0;j < n; j++){
                if(G[i][j] == '0'){
                    f[i][j] = up[i][j] + down[i][j] + right[i][j] + left[i][j];
                    res = Math.max(res, f[i][j]);
                }
            }
        }
        return res;
    }
}

输入输出：

样例
样例1

输入:
grid =[
     "0E00",
     "E0WE",
     "0E00"
]
输出: 3
解释:
把炸弹放在 (1,1) 能杀3个敌人
样例2

输入:
grid =[
     "0E00",
     "EEWE",
     "0E00"
]
输出: 2

本文地址：https://blog.csdn.net/lynn_Dai/article/details/107312270

您可能感兴趣的文章:

如对本文有疑问，点击进行留言回复！！

springcloud中feign调用处理mybatis-plus Ipage反序列化问题。

通过feign接口返回的分页列表IPage，出现报错，具体报错内容如下：feign.codec.DecodeEx... [阅读全文]
大数据云计算——Azkaban组件

什么是 AzkabanAzkaban 是由 Linkedin 公司推出的一个批量工作流任务调度器，主要用于在一个... [阅读全文]
荐聊聊数据库表结构设计心得

本文讨论是一般表的设计，有一定的普遍性和通用性，当然对于特殊性的考量则不在本文讨论之列。自增 idJava 层的... [阅读全文]
SpringCloud各个组件最强总结

一、概念1.1 什么是Spring Cloud？Spring Cloud就是微服务系统架构的一站式解决方案，在平... [阅读全文]
微服务之SpringCloud

# 微服务介绍将一个原本独立的系统拆分成多个小型服务，这些小型服务都在各自独立的进程中运行，并使用轻量级机制通信... [阅读全文]
劝退记：如你如我，平庸且不甘 | 年中总结

关于我前端劝退师，最近也叫前端失业师。没能力没学历没背景，三无前端。工作第四年，想和优秀的一批人竞争，永远和自己... [阅读全文]
Flume 史上最全面的大数据学习第十篇（一）别再说不知道flume是什么了

昨天没有增加小粉丝，我反思了一下自己，是不是我写的东西太过枯燥了呀！挺难受的！算了还是不说了，每天都是美好的一天... [阅读全文]
一直想学习Java网络编程，却不知道怎么入门？

其实，我刚学习Netty的时候，也是很迷茫的，直到有一天，一个同事收到了阿里的offer，他要去阿里做中台了，临... [阅读全文]
SpringCloud相关笔记一系统架构的演变(一)

SpringCloudSpringBoot 四种属性注入小结1.@Autowired注入2.构造方法注入3.@B... [阅读全文]
面试官：说说Kafka控制器事件处理全流程

前言大家好，我是 yes。这是Kafka源码分析第四篇文章，今天来说说 Kafka控制器，即 Kafka Con... [阅读全文]