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

程序员文章站 2022-07-10 16:22:48

动态规划的题目特点1、计数型有多少种方式走到右下脚有多少种方法选出k个数的和是sum2、求最大值最小值型从左上角走到右下角路径的最大数字和最长上升子序列长度3、求存在性型取石子游戏，先手是否必胜能不能选出k个数使得和为sum动态规划的总结1、确定状态研究最优策略的最后一步化为子问题2、转移方程根据子问题定义直接得到3、初始条件和边界条件细心、考虑周全4、计算顺序利用之前的计算结果例题解析及其代码例题一：求最大值最小值型题目：你有三种硬币，分别面值...

动态规划的题目特点

计数型
有多少种方式走到右下脚
有多少种方法选出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

上一篇： ps cs5怎么设计玻璃化的七彩花瓣效果?

下一篇：大一C语言大作业--扫雷雷

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

动态规划的题目特点

动态规划的总结

1、确定状态

2、转移方程

3、初始条件和边界条件

4、计算顺序

例题解析及其代码

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

例题二：计数型

例题三：求存在性型

例题四：求最值型

例题五：坐标型

例题六：序列型

例题七：划分型

例题八：序列型

例题九：求最值型

例题十：坐标型

菜鸟学习笔记：Java提升篇12（Java动态性2——动态编译、javassist字节码操作）

荐 javascript从入门到跑路-----小文的js学习笔记（17）------动态属性、复制变量值、传递参数和检测类型

[ExtJS5学习笔记]第二十九节 sencha ext js 5.1.0中动态更换皮肤主题

mybatis学习笔记之动态sql

剑指 Offer 42. 连续子数组的最大和——从这题开始学习动态规划

Spring学习笔记_AOP的cglib动态代理底层实现方式

编译原理学习笔记 7.3 动态存储分配

数据结构与算法学习笔记：动态数组

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

卜若的代码笔记-算法系列-第3个算法案例分析：斐波那契最长动态规划算法