锐客网

  1. 首页 > it技术 > >

算法之《动态规划》练习解析

动态规划概念篇 定义：动态规划是分治思想的延伸，通俗一点来说就是大事化小，小事化无的艺术。通过拆分问题、定义问题状态和状态间的关系，让问题用递推的方式得到结局；
特点和考虑维度：
①把原来的问题分解成了几个相似的子问题。
② 所有的子问题都只需要解决一次。
③ 储存子问题的解。
动态规划的本质，是对问题状态的定义和状态转移方程的定义
动规一般都需要和数组搭配使用
动态规划问题一般从以下四个角度考虑：
状态定义、状态间的转移方程定义、状态的初始化、 返回结果
适用场景：最大/最小值 、可行不可行、是不是、方案个数等

个人看法：其实这些概念我感觉看看就好，因为在你没有做很多动规题之前，再看这些概念也是纸上谈兵，也不会对动规有很好的理解和掌握，只有做的多了，自不然就明白动规是咋回事，也就会用了；emmm,我滚去刷题了，我会把题目链接附上，大家感兴趣可以去做一下，毕竟实践出真知哈
实际练习篇 1、斐波那契数列
题目链接：牛客网剑指offerJZ7；现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）
解析：这个是最简单也是最经典的动规问题，拿上面的概念去套，要求第n个，相似的子问题，就是需要知道第n项的前两个，他们之间可以递推，
public class Solution { public int Fibonacci(int n) { if(n<=0){ return 0; } int arr[]=new int[n+1]; //保存子问题的解 arr[0]=0; //这两个就是状态的初始化 arr[1]=1; for(int i=2; i<=n; i++){ arr[i]=arr[i-1]+arr[i-2]; //状态转移方程 } return arr[n]; } }

2、牛妹的蛋糕
题目链接：牛客网-牛牛吃蛋糕；众所周知，牛妹非常喜欢吃蛋糕。第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一多一个，以后每天吃掉前一天剩下的三分之一多一个，到第n天准备吃的时候只剩下一个蛋糕。牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？
解析：最后一天时剩一个，从最后一天往前推，找递推公式，分析题意，假设今天有蛋糕y个，前一天有x个。则y = x*2/3-1，所以就能得出x=3(y+1)/2。
import java.util.*; public class Solution { public int cakeNumber (int n) { if(n==1){ return 1; } int sum=1; //初始值 for(int i=n; n>1; n--){//从第n天开始往前推 sum=3*(sum+1)/2; } return sum; } }

3、连续子数组的最大和
题目链接：牛客网-剑指offer原题：{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
解析：从第一个开始，每往进加一个就要去判断现在的总和跟没加之前相比哪个大；
public class Solution { public int FindGreatestSumOfSubArray(int[] array) { int result=array[0]; //保留当前最大值 int max=array[0]; //包含arr[i]的连续数组最大值 for(int i=1; i

4、单词分割
题目链接：牛客网-单词分割；给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。
例如：给定s=“leetcode”；dict=[“leet”, “code”]。返回true，因为"leetcode"可以被分割成"leet code".
解析：分解成子问题就是数组中后面的包含在内，那位于前面的一定要包含在内，所以我们就需要去判断每一个是否包含在内；
import java.util.Set; public class Solution { public boolean wordBreak(String s, Set dict) { boolean[] arr=new boolean[s.length()+1]; //用boolean类型的数组去记录单个的是否被包含 arr[0]=true; //假设一个初始值 for(int i=1; i<=s.length(); i++){ for(int j=i-1; j>=0; j--){ if(arr[j]&&dict.contains(s.substring(j,i))){ arr[i]=true; break; } } } return arr[s.length()]; } }

5、机器人走方格
题目链接：牛客网-机器人走方格；一个机器人在m×n大小的地图的左上角（起点，下图中的标记“start"的位置）。机器人每次向下或向右移动。机器人要到达地图的右下角。（终点，下图中的标记“Finish"的位置）。
可以有多少种不同的路径从起点走到终点？
算法之《动态规划》练习解析
文章图片

解析：划分为子状态就是从(0,0)到达(1,0),(1,1),(2,1),…(m-1,n-1)的路径数；F(i,j): 从(0,0)到达F(i,j)的路径数
状态递推：F(i,j) = F(i-1,j) + F(i,j-1)
import java.util.*; public class Solution { public int uniquePaths (int m, int n) { if(m==0||n==0) return 0; int[][] arr=new int[m][n]; for(int i=1; i

6、01背包问题
题目链接：背包问题，笔试还是很常见的；有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值。问最多能装入背包的总价值是多大?
样例 1:
输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]
输出: 9
解释: 装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9
解析：
F(i, j)是前i个物品放入大小为j的背包中所获得的最大价值
状态递推：对于第i个商品，有一种例外，装不下，两种选择，放或者不放； 如果装不下：此时的价值与前i-1个的价值是一样的
F(i,j) = F(i-1,j)
如果可以装入：需要在两种选择中找最大的
F(i, j) = max{F(i-1,j), F(i-1, j - A[i]) + V[i]}
F(i-1,j): 表示不把第i个物品放入背包中， 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值
F(i-1, j - A[i]) + V[i]：表示把第i个物品放入背包中，价值增加V[i],但是需要腾出j - A[i]的大小放
第i个商品
初始化：第0行和第0列都为0，表示没有装物品时的价值都为0
F(0,j) = F(i,0) = 0
返回值：F(n,m)
public class Solution { public int backPackII(int m, int[] A, int[] V) { // write your code here int len=A.length; int[][] maxValue=https://www.it610.com/article/new int[len+1][m+1]; for(int i=0; i<=num; i++){//进行初始化 maxValue[i][0]=0; } for(int i=1; i<=num; i++){ maxValue[0][i]=0; } for(int i=1; i<=num; i++){ for(int j=1; j<=num; j++){ if(A[i-1]>j){//说明放不下 maxValue[i][j] = maxValue[i - 1][j]; //装不下时value值不变 } else{ //能装下时看你愿不愿意装，装的话就腾出第i个物品 int new=maxValue[i-1][j-A[i-1]]+V[i-1]; maxValue[i][j]=Math.max(new,maxValue[i-1][j]); } } } return maxValue[num][m]; } }

7、回文串分割
【算法之《动态规划》练习解析】题目链接：牛客网-回文串分割
给出一个字符串s，分割s使得分割出的每一个子串都是回文串
计算将字符串s分割成回文分割结果的最小切割数
例如:给定字符串s=“aab”,
返回1，因为回文分割结果[“aa”,“b”]是切割一次生成的。
import java.util.*; public class Solution { public boolean isPal(String s,int start,int end){ while(start

    推荐阅读


    上一篇：树相关总结（二叉树、AVL树、红黑树、B树、B+树）

    下一篇：作业帮一面+二面+（等下周hr面面完再来把hr面加上）