动态规划:动态规划,无非就是利用历史记录,来避免我们的重复计算。而这些历史记录,我们得需要一些变量来保存,一般是用一维数组或者二维数组来保存。
动态规划的三大步骤:
问题描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
(1)、定义数组元素的含义
按我上面的步骤说的,首先我们来定义 dp[i] 的含义,我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法,那我们就定义 dp[i] 的含义为:跳上一个 i 级的台阶总共有 dp[i] 种跳法。这样,如果我们能够算出 dp[n],不就是我们要求的答案吗?所以第一步定义完成。
(2)、找出数组元素间的关系式
我们的目的是要求 dp[n],动态规划的题,如你们经常听说的那样,就是把一个规模比较大的问题分成几个规模比较小的问题,然后由小的问题推导出大的问题。也就是说,dp[n] 的规模为 n,比它规模小的是 n-1, n-2, n-3…. 也就是说,dp[n] 一定会和 dp[n-1], dp[n-2]….存在某种关系的。我们要找出他们的关系。
那么问题来了,怎么找?
这个怎么找,是最核心最难的一个,我们必须回到问题本身来了,来寻找他们的关系式,dp[n] 究竟会等于什么呢?
对于这道题,由于情况可以选择跳一级,也可以选择跳两级,所以青蛙到达第 n 级的台阶有两种方式
一种是从第 n-1 级跳上来
一种是从第 n-2 级跳上来
由于我们是要算所有可能的跳法的,所以有 dp[n] = dp[n-1] + dp[n-2]。
(3)、找出初始条件
当 n = 1 时,dp[1] = dp[0] + dp[-1],而我们是数组是不允许下标为负数的,所以对于 dp[1],我们必须要直接给出它的数值,相当于初始值,显然,dp[1] = 1。一样,dp[0] = 0.(因为 0 个台阶,那肯定是 0 种跳法了)。于是得出初始值:dp[0] = 0.
注:分析是有问题的,因为i=2,dp[2]=2;错在对初始值的寻找不够严谨,
int f(int n){ int[] dp = new int[n + 1]; // 给出初始值 dp[0] = 0; dp[1] = 1; dp[2] = 2; // 通过关系式来计算出 dp[n] for(int i = 3; i <= n; i++){ dp[i] = dp[i-1] + dp[i-2]; } // 把最终结果返回 return dp[n]; }
问题描述:
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径?(m、n值均不超过100)
还是老样子,三个步骤来解决。
步骤一、定义数组元素的含义
由于我们的目的是从左上角到右下角一共有多少种路径,那我们就定义 dp[i] [j]的含义为:当机器人从左上角走到(i, j) 这个位置时,一共有 dp[i] [j] 种路径。那么,dp[m-1] [n-1] 就是我们要的答案了。
注意,这个网格相当于一个二维数组,数组是从下标为 0 开始算起的,所以 右下角的位置是 (m-1, n - 1),所以 dp[m-1] [n-1] 就是我们要找的答案。
步骤二:找出关系数组元素间的关系式
想象以下,机器人要怎么样才能到达 (i, j) 这个位置?由于机器人可以向下走或者向右走,所以有两种方式到达
一种是从 (i-1, j) 这个位置走一步到达
一种是从(i, j - 1) 这个位置走一步到达
因为是计算所有可能的步骤,所以是把所有可能走的路径都加起来,所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。
步骤三、找出初始值
显然,当 dp[i] [j] 中,如果 i 或者 j 有一个为 0,那么还能使用关系式吗?答是不能的,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了,所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的,相当于计算机图中的最上面一行和左边一列。因此初始值如下:
dp[0] [0….n-1] = 1; // 相当于最上面一行,机器人只能一直往左走
dp[0…m-1] [0] = 1; // 相当于最左面一列,机器人只能一直往下走
public static int calc(int m, int n) { if (m <= 0 || n <= 0) { return 0; } int[][] dp = new int[m][n]; for(int i = 0; i < m; i++){ dp[i][0] = 1; } for(int i = 0; i < n; i++){ dp[0][i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; }
问题描述:给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
示例 1: 输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
解答
还是老样子,按照上面三个步骤来,并且我这里可以告诉你,90% 的字符串问题都可以用动态规划解决,并且90%是采用二维数组。
步骤一、定义数组元素的含义
由于我们的目的求将 word1 转换成 word2 所使用的最少操作数 。那我们就定义 dp[i] [j]的含义为:当字符串 word1 的长度为 i,字符串 word2 的长度为 j 时,将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]。
有时候,数组的含义并不容易找,所以还是那句话,我给你们一个套路,剩下的还得看你们去领悟。
步骤二:找出关系数组元素间的关系式
接下来我们就要找 dp[i] [j] 元素之间的关系了,比起其他题,这道题相对比较难找一点,但是,不管多难找,大部分情况下,dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。因为我们的目标就是,从规模小的,通过一些操作,推导出规模大的。对于这道题,我们可以对 word1 进行三种操作
插入一个字符
由于我们是要让操作的次数最小,所以我们要寻找最佳操作。那么有如下关系式:
一、如果我们 word1[i] 与 word2 [j] 相等,这个时候不需要进行任何操作,显然有 dp[i] [j] = dp[i-1] [j-1]。(别忘了 dp[i] [j] 的含义哈)。
二、如果我们 word1[i] 与 word2 [j] 不相等,这个时候我们就必须进行调整,而调整的操作有 3 种,我们要选择一种。三种操作对应的关系试如下(注意字符串与字符的区别):
(1)、如果把字符 word1[i] 替换成与 word2[j] 相等,则有 dp[i] [j] = dp[i-1] [j-1] + 1;
(2)、如果在字符串 word1末尾插入一个与 word2[j] 相等的字符,则有 dp[i] [j] = dp[i] [j-1] + 1;
(3)、如果把字符 word1[i] 删除,则有 dp[i] [j] = dp[i-1] [j] + 1;
那么我们应该选择一种操作,使得 dp[i] [j] 的值最小,显然有
dp[i] [j] = min(dp[i-1] [j-1],dp[i] [j-1],dp[[i-1] [j]]) + 1;
于是,我们的关系式就推出来了,
步骤三、找出初始值
显然,当 dp[i] [j] 中,如果 i 或者 j 有一个为 0,那么还能使用关系式吗?答是不能的,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了,所以我们的初始值是计算出所有的 dp[0] [0….n] 和所有的 dp[0….m] [0]。这个还是非常容易计算的,因为当有一个字符串的长度为 0 时,转化为另外一个字符串,那就只能一直进行插入或者删除操作了。
public int minDistance(String word1, String word2) { int n1 = word1.length(); int n2 = word2.length(); int[][] dp = new int[n1 + 1][n2 + 1]; // dp[0][0...n2]的初始值 for (int j = 1; j <= n2; j++) { dp[0][j] = dp[0][j - 1] + 1; } // dp[0...n1][0] 的初始值 for (int i = 1; i <= n1; i++) { dp[i][0] = dp[i - 1][0] + 1; } // 通过公式推出 dp[n1][n2] for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { // 如果 word1[i] 与 word2[j] 相等。第 i 个字符对应下标是 i-1 if (word1.charAt(i - 1) == word2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1; } } } return dp[n1][n2]; }
来自牛客网
描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
示例1
输入:
2
返回值:
2
复制
示例2
输入:
7
返回值:
21
解法
这是一道经典的递推题目,你可以想如果青蛙当前在第n级台阶上,那它上一步是在哪里呢?
显然,由于它可以跳1级台阶或者2级台阶,所以它上一步必定在第n-1,或者第n-2级台阶,也就是说它跳上n级台阶的跳法数是跳上n-1和跳上n-2级台阶的跳法数之和。
设跳上 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2XJP1Il9-1632038238167)(https://www.nowcoder.com/equation?tex=i&preview=true)] 级台阶有 fun(n) 种跳法,则它跳上n级的台阶有 fun(n) = fun(n-1)+fun(n-2) 种跳法。
然后,我们又思考初始的情况,跳上1级台阶只有1种跳法,跳上2级台阶有2种跳法,最终我们得到如下的递推式,这个递推式和 斐波那契比较相似。
笔试不推荐递归,可以采用斐波那契的解法二或解法三(解法二的改良)
if (target == 1 || target == 2) { return target; } int a = 1, b = 2, c = 0; for (int i = 2; i < target; i++) { c = a + b; a = b; b = c; } return c;
public static int jumpFloor(int target) { int a = 1, b = 1; for (int i = 2; i <= target; i++) { a=a+b; b=a-b; } return a; }
描述
给定一个数组arr,返回子数组的最大累加和
例如,arr = [1, -2, 3, 5, -2, 6, -1],所有子数组中,[3, 5, -2, 6]可以累加出最大的和12,所以返回12.
题目保证没有全为负数的数
示例1
输入:
[1, -2, 3, 5, -2, 6, -1]
返回值:
12
解法一:动态规划
public int maxsumofSubarray(int[] arr) { if (arr.length == 0) { return 0; } int[] dp = new int[arr.length]; dp[0] = arr[0]; int max = dp[0]; for (int i = 1; i < dp.length; i++) { dp[i] = dp[i - 1] > 0 ? dp[i - 1] + arr[i] : arr[i]; max=Math.max(max,dp[i]); } return max; }
动态规划改良
public int maxsumofSubarray(int[] arr) { if (arr.length == 0) { return 0; } int sum = arr[0]; int max = sum; for (int i = 1; i < arr.length; i++) { sum = sum > 0 ? sum + arr[i] : arr[i]; max = Math.max(max, sum); } return max; }
描述
假设你有一个数组,其中第 i 个元素是股票在第 i 天的价格。
你有一次买入和卖出的机会。(只有买入了股票以后才能卖出)。请你设计一个算法来计算可以获得的最大收益。
示例1
输入:
[1,4,2]
返回值:
3
示例2
输入:
[2,4,1]
返回值:
2
解法一:动态规划
dp[i]表示前i日的最大利润。
则转移方程为:
dp[i] = max( dp[i-1], prices[i] - min(prices[0 -> i]))。
也就是说,每日的最大利润为以下两项的大者:
初始:
dp[0] = 0;
返回值:
dp[prices.length - 1]
public static int maxProfit(int[] prices) { if (prices.length == 0) { return 0; } int maxPro = 0; int min = prices[0]; for (int i = 1; i < prices.length; i++) { maxPro = Math.max(maxPro, prices[i] - min); min = Math.min(min, prices[i]); } return maxPro; }
解法二:动态规划改良(双指针)
用两个指针,一个指针记录访问过的最小值(注意这里是访问过的最小值),一个指针一直往后走,然后计算他们的差值,保存最大的即可
public static int maxProfit(int[] prices) { if (prices.length == 0) { return 0; } int min = prices[0]; int maxPro = 0; for (int i = 1; i < prices.length; i++) { min = Math.min(min, prices[i]); maxPro = Math.max(prices[i] - min, maxPro); } return maxPro; }
描述
给定数组arr,arr中所有的值都为正整数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个aim,代表要找的钱数,求组成aim的最少货币数。
如果无解,请返回-1.
【要求】
时间复杂度O(n \times aim)O(n×aim),空间复杂度On。
示例1
输入:
[5,2,3],20
返回值:
4
示例2
输入:
[5,2,3],0
返回值:
0
示例3
输入:
[3,5],2
返回值:
-1
备注
0≤n≤1000 0≤aim≤5000
解法:动态规划
public static int minMoney(int[] arr, int aim) { int max = aim + 1; //定义一个全局变量 int[] dp = new int[aim + 1]; //dp[i]的含义是目标值为i的时候最少钱币数是多少 Arrays.fill(dp, max); //把dp数组全部定义为最大值 dp[0] = 0; for (int i = 0; i <= aim; i++) { //遍历目标值 for (int j = 0; j < arr.length; j++) { //遍历钱币 if (arr[j] <= i) { //如果当前钱币比目标值小就可以兑换 dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1); } } } return dp[aim] > aim ? -1 : dp[aim]; }
描述
已知一个背包最多能容纳物体的体积为 V
现有 N 个物品,第 i 个物品的体积为Vi, 重量为 Wi
求当前背包最多能装多大重量的物品?
数据范围:
示例1
输入:
10,2,[[1,3],[10,4]]
返回值:
4
说明:
第一个物品的体积为1,重量为3,第二个物品的体积为10,重量为4。只取第二个物品可以达到最优方案,取物重量为4
解法:动态规划
面对每个物品,我们只有选择拿取或者不拿两种选择,不能选择装入某物品的一部分,也不能装入同一物品多次。
**解决办法:**声明一个大小为 dp[n][V] 的二维数组, dp[i][j] 表示 在面对第 i 件物品,且背包容量为 j 时所能获得的最大价值 ,那么我们可以很容易分析得出dp[i][j] 的计算方法
(1) j < w[i] 的情况,这时候背包容量不足以放下第 i 件物品,只能选择不拿 dp[ i ][ j ] = dp[ i-1 ][ j ]
(2) j>=w[i] 的情况,这时背包容量可以放下第 i 件物品,我们就要考虑拿这件物品是否能获取更大的价值。
究竟是拿还是不拿,自然是比较这两种情况那种价值最大。
由此可以得到状态转移方程
if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); else dp[i][j]=dp[i-1][j];
根据题意修改得到:
public static int knapsack(int V, int n, int[][] vw) { if (V == 0 || n == 0 || vw == null) { return 0; } int[][] dp = new int[n + 1][V + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= V; j++) { if (j < vw[i - 1][0]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]); } } } return dp[n][V]; }
描述
给定一个数组arr,返回arr的最长无重复元素子数组的长度,无重复指的是所有数字都不相同。
子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组
示例1
输入:
[2,3,4,5]
返回值:
4
说明:
[2,3,4,5]是最长子数组
示例2
输入:
[2,2,3,4,3]
返回值:
3
说明:
[2,3,4]是最长子数组
示例3
输入:
[9]
返回值:
1
示例4
输入:
[1,2,3,1,2,3,2,2]
返回值:
3
说明:
最长子数组为[1,2,3]
示例5
输入:
[2,2,3,4,8,99,3]
返回值:
5
说明:
最长子数组为[2,3,4,8,99]
解法一: 双指针+回头遍历( 动态规划改良)
public static int maxLength1(int[] arr) { int tmp = 0, res = 0; for (int right = 0; right < arr.length; right++) { int left = right - 1; while (left >= 0 && arr[left] != arr[right]) { left--; } tmp = tmp < right - left ? tmp + 1 : right - left; res = Math.max(res, tmp); } return res; }
解法二: 滑动窗口
public static int maxLength(int[] arr) { if (arr.length < 2) { return arr.length; } HashMap<Integer, Integer> map = new HashMap<>(); int res = 0; int left = -1; for (int right = 0; right < arr.length; right++) { if (map.containsKey(arr[right])) { left = Math.max(left, map.get(arr[right])); } res = Math.max(res, right - left); map.put(arr[right], right); } return res; }
描述
给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。
示例1
输入:
"1AB2345CD","12345EF"
返回值:
"2345"
解法:动态规划
对于字符串str1
(长度为m
)和str2
(长度为n
),我们可以使用一个二维整形数组(m
* n
)实现动态规划算法。
思路:
dp[i][j]
:表示在str1
中以坐标i
结尾的子串与str2
中以坐标j
结尾的子串,最长公共子串的长度(从i
,j
的位置往前推)
递推方程:
str1
第i
个字符不等于str2
第j
个字符,那么dp[i][j] = 0
dp[i][j] = dp[i-1]d[j-1] + 1
关于字符串的截取:
使用一个整型变量maxLength
来记录当前的最长公共子串的长度
使用一个整型变量lastIndex
来指向str1
中当前最长公共子串的最后一个字符的下标
public static String LCS(String str1, String str2) { int m = str1.length(); int n = str2.length(); int[][] dp = new int[m][n]; int maxLength = 0; int lastIndex = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (str1.charAt(i) == str2.charAt(j)) { if (i == 0 || j == 0) { dp[i][j] = 1; } else { dp[i][j] = dp[i - 1][j - 1] + 1; } if (dp[i][j] > maxLength) { maxLength = dp[i][j]; lastIndex = i; } } } } return str1.substring(lastIndex - maxLength + 1, lastIndex + 1); }