1. 首页
  2. 文章中心
  3. 算法学习

（基于Java）算法笔记——动态规划算法

77 阅读 0 评论
我是靠谱客的博主 友好钢笔，最近开发中收集的这篇文章主要介绍（基于Java）算法笔记——动态规划算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

动态规划算法的简单学习笔记

1、算法解释

动态规划（Dynamic Programming，DP）

  • 查找很多重叠子问题的最优解
    （最优子结构：局部最优解能决定全局最优解）
    • 将大问题重组为许多子问题
    • 每个子问题的结果被保存，累积下来即为解决大问题、
    • 关键是：状态转移方程
    • 进行空间压缩，节省空间消耗
  • 自上而下与自下而上
    • 动态规划：自上而下，先解决子问题，再解决父问题；适合求最终状态的问题
    • 带状态记录的优先搜索：自下而上，从父问题到子问题；适合输出所有符合的路径

2、一维动态规划

① LeetCode 70 爬楼梯

解题思路

  • 题意为：爬上N阶楼梯共有多少种方法
    • 分解为子问题：爬上第i阶楼梯有多少种方法，设为dp[i]
  • 因为第i阶，可由i-1阶或i-2阶上来，所以有dp[i] = dp[i-1] + dp[i-2]

Java解答

class Solution {
public int climbStairs(int n) {
if(n <= 2) return n;
int[] dp = new int[n];
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}
}

② LeetCode 198 打家劫舍

解题思路

  • 对于第K间屋子是否打劫：
    • 若打劫，则前面的累积至K-2间都打劫了
    • 若不打劫，则仅打劫了前面累积至K-1间
  • 到达当前屋子i时，设最大累积打劫金额为dp[i]
    • 若第i间打劫，则dp[i] = dp[i-2]+nums[i]
    • 若第i间不打劫，则dp[i] = dp[i-1]

Java解答

class Solution {
public int rob(int[] nums) {
int len = nums.length;
if (nums == null || len == 0) {
return 0;
}
if (len == 1) {
return nums[0];
}
int[] dp = new int[len];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < len; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[len-1];
}
}

③ LeetCode 413 等差数列划分

解题思路

  • 注意：等差子数组，各元素在原数组中必须连续
  • 每当有一个子数组时，总和累计

Java解答

class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int len = nums.length;
int sum = 0;
int[] dp = new int[len];
for (int i = 2; i < len; i++) {
if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
dp[i] = 1 + dp[i-1];
sum += dp[i];
}
}
return sum;
}
}

3、二维动态规划

① LeetCode 64 最小路径和

解题思路

  • 设当前位置的dp[i][j]为此前的路径最小和
    • dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
  • 由于对于已经遍历过的j列，不会再遍历
    • 由此，可以通过空间压缩，将dp二维将为一位，提升算法

Java解答

class Solution {
public int minPathSum(int[][] grid) {
int row = grid.length, col = grid[0].length;
int[] dp = new int[col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == 0 && j == 0) {
dp[j] = grid[i][j];
} else if (i == 0) {
dp[j] = dp[j-1] + grid[i][j];
} else if (j == 0) {
dp[j] = dp[j] + grid[i][j];
} else {
dp[j] = Math.min(dp[j], dp[j-1]) + grid[i][j];
}
}
}
return dp[col-1];
}
}

② LeetCode 542 0-1矩阵

解题思路

  • 需要四个方向的搜索
  • 为避免重复遍历相同位置，从右下、左上两个方向两次遍历

Java解答

class Solution {
public int[][] updateMatrix(int[][] mat) {
int row = mat.length, col = mat[0].length;
int dp[][] = new int[row][col];
for (int i = 0; i < row; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE-1);
}
// 右下遍历一次
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (mat[i][j] == 0) {
dp[i][j] = 0;
} else {
if (j > 0) {
dp[i][j] = Math.min(dp[i][j], dp[i][j-1]+1);
}
if (i > 0) {
dp[i][j] = Math.min(dp[i][j], dp[i-1][j]+1);
}
}
}
}
// 左上遍历一次
for (int i = row-1; i >= 0; i--) {
for (int j = col-1; j >= 0; j--) {
if (mat[i][j] != 0) {
if (j < col - 1) {
dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
}
if (i < row - 1) {
dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
}
}
}
}
return dp;
}
}

③ LeetCode 221 最大正方形

解题思路

  • 设dp[i][j]表示满足条件的正方形右下角，值为该正方形的边长
    • 以(i, j)当前位置为右下角，判断左、上以及左上的值，是否比当前位置小1
    • 不断更新记录最大边长，返回其平方

Java解答

class Solution {
public int maximalSquare(char[][] matrix) {
int row = matrix.length, col = matrix[0].length;
int[][] dp = new int[row+1][col+1];
int square_side = 0;
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= col; j++) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
}
square_side = Math.max(square_side, dp[i][j]);
}
}
return square_side * square_side;
}
}

4、分割类型问题

① LeetCode 279 完全平方数

解题思路

  • 动态规划的思路其实是全部遍历一遍
    • 从 1 开始，到 n 结束；更新每个数能最少由多少个平方数组成
    • 采取判断的方法，举例说明：如对于数字 9
      • 先 9 - 1*1 = 8，由于 8 在之前遍历中，仅需 2 个平方数（dp[8]=2），记录最小为2
      • 再 9 - 2*2 = 5，由于 5 在之前遍历中，仅需 2 个平方数（dp[5]=2），与上一个比较，仍为2
      • 再 9 - 3*3 = 0，由于 0 位置所指为0，记录最小为 dp[0] = 0
      • 再 9 < 4*4，结束遍历
      • 因此数字 9 需要 0 + 1 = 1 个平方数，即dp[9] = 1
    • 再举例，如数字 34
      • 34 - 1*1 = 33，dp[33] = 3，记录最小为 3
      • 34 - 2*2 = 30，dp[30] = 3，最小为 3
      • 34 - 3*3 = 25，dp[25] = 1，最小为 1
      • 34 - 4*4 = 18，dp[18] = 2，最小仍为 1
      • 34 - 5*5 = 9，dp[9] = 1，最小为 1
      • 34 < 6*6，结束遍历
      • 因此数字 34 需要 1 + 1 = 2 个平方数，即dp[34] = 2

Java解答

class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; j++) {
min = Math.min(min, dp[i - j * j]);
}
dp[i] = min + 1;
}
return dp[n];
}
}

② LeetCode 91 解码方法

解题思路

  • 对字符串各元素遍历
    • 若当前元素不为 0 ，dp[i] = dp[i] + dp[i-1]；
      • 接着，判断当前元素和前一个元素是否符合，则再 dp[i] = dp[i] + dp[i-2]；
    • 若当有元素为0，跳过不计

Java解答

class Solution {
public int numDecodings(String s) {
int len = s.length();
int[] dp = new int[len+1];
dp[0] = 1;
for (int i = 1; i <= len; i++) {
if (s.charAt(i-1) != '0') {
dp[i] += dp[i-1];
}
if (i > 1 && s.charAt(i-2) != '0' && ((s.charAt(i-2) - '0') * 10 + (s.charAt(i-1)-'0') <= 26)) {
dp[i] += dp[i-2];
}
}
return dp[len];
}
}

③ LeetCode 139 单词拆分

解题思路

  • 设dp[i] 表示从头开始的长度为 i 的‘单词’是否存在
    • dp[i]为真的条件，举例说明，假如一字符串：“catdoghorsetigerfish…”
      • j = 6, i =10 时，(j, i)分割的单词为"horse"，存在
      • 并且dp[j]=true，即"catdog"在之前的判断中已经赋为真
  • 判断条件的伪代码：dp[j] && string.sub(j, i).contains

Java解答

class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int len = s.length();
boolean[] dp = new boolean[len+1];
dp[0] = true;
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
}

5、子序列问题

① LeetCode 300 最长递增子序列

解题思路

  • 设dp[i]为前i个元素所能包括的最长递增子序列长度

Java解答

class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
int res = 0;
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
res = Math.max(res, dp[i]);
}
return res + 1;
}
}

// 动态规划 + 二分查找
// 设dp[i]为长度等于i+1的递增子序列的最后一个数字（要最小的）
class Solution {
public int lengthOfLIS(int[] nums) {
int len = 1, n = nums.length;
if (n == 0) {
return 0;
}
int[] d = new int[n + 1];
d[len] = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) {
d[++len] = nums[i];
} else {
int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
}
}
return len;
}
}

② LeetCode 最长公共子序列

解题思路

  • 设dp[i][j]为text1[0:i]与text2[0:j]的最长公共子序列

Java解答

class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
char[] t1 = text1.toCharArray();
char[] t2 = text2.toCharArray();
int pre = 0;
int k = 0;
int[] dp = new int[m];
for(int i = 0; i < n; i++){
pre = 0;
k = 0;
for(int j = 0; j < m; j++){
if(t1[i] == t2[j])
k = pre + 1;
else
k = Math.max(dp[j], k);
pre = dp[j];
dp[j] = k;
}
}
return dp[m-1];
}
}

6、背包问题

背包问题解释

  • N个物品，每个体积为v、价值为w
  • 一个背包其容量体积为V
  • 使背包装下物品的总价值最大
  • 设dp[i][j]为前i件物品体积不超过j的情况下达到的最大价值
    • 若不放入第i件物品，dp[i][j] = dp[i-1][j]，价值为前i-1件的最大价值
    • 若放入第i件物品，dp[i][j] = dp[i-1][j-v] + w
    • 遍历过程中取最大值

① LeetCode 416 分割等和子集

解题思路

  • 总和为奇、总和的一半比数组最大值还大，都直接返回false
  • 以nums的每个值为价值，以总和的一半为体积，进行NP动态规划

Java解答

class Solution {
public boolean canPartition(int[] nums) {
int len = nums.length;
int sum = 0, target = 0;
for (int i = 0; i < len; i++) {
sum += nums[i];
}
if (sum % 2 == 0) {
target = sum / 2;
} else {
return false;
}
int[][] dp = new int[len+1][target+1];
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= target; j++) {
if (j < nums[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i-1]]+nums[i-1]);
}
if (dp[i][j] == target) {
return true;
}
}
}
return false;
}
}

② LeetCode 474 一和零

解题思路

  • 由于判断两个变量的变化，则设dp为dp[i][j][k]，进行状态转移

Java解答

class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int[][][] dp = new int[len+1][m+1][n+1];
for (int i = 1; i <= len; i++) {
int[] subMN = mAndn(strs[i-1]);
int subM = subMN[0], subN = subMN[1];
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= n; k++) {
dp[i][j][k] = dp[i-1][j][k];
if (j >= subM && k >= subN) {
dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-subM][k-subN]+1);
}
}
}
}
return dp[len][m][n];
}
private int[] mAndn(String str) {
int m=0, n=0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '0') {
m++;
} else {
n++;
}
}
return new int[]{m, n};
}
}

③ LeetCode 322 零钱兑换

解题思路

  • 计算dp[i]之前，我们已经计算出dp[0]~dp[1]的答案
  • dp[i] = min(dp[i-coin[j])+1

Java解答

class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 3);
dp[0] = 0;
for (int i = 0; i < coins.length; i++) {
int coin = coins[i];
for (int j = coin; j <= amount; j++) {
if (dp[j - coin] != amount + 3) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
}
if (dp[amount] == amount + 3) {
return -1;
}
return dp[amount];
}
}

7、字符串编辑问题

① LeetCode 72 编辑距离

解题思路

  • dp[i][j]表示第一个字符串到位置i为止，第二个字符串到位置j为止，最多需要编辑几步
  • 当第i位字符和第j位字符相同时，dp[i][j] = dp[i-1][j-1]，否则
    • 修改字符，dp[i][j] = dp[i-1][j-1]+1
    • 插入i位置/删除j位置，dp[i][j] = dp[i][j-1] + 1
    • 插入j位置/删除i位置，dp[i][j] = dp[i-1][j] + 1

Java解答

class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else {
dp[i][j] = Math.min(dp[i-1][j-1] + ((word1.charAt(i-1) == word2.charAt(j-1) ? 0 : 1)), Math.min(dp[i-1][j]+1, dp[i][j-1]+1));
}
}
}
return dp[m][n];
}
}

② LeetCode 650 只有两个键的键盘

解题思路

  • 对每一个格子i，如果i可以被j除尽，说明j个A可以通过复制粘贴得到i个A，复制粘贴次数为i / j
  • dp[i] = min(dp[i], dp[j] + i / j)dp[i]=min(dp[i],dp[j]+i/j)

Java解答

class Solution {
public int minSteps(int n) {
int[] dp = new int[n+1];
Arrays.fill(dp, n+1);
dp[1] = 0;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i / 2; j++) {
if (i % j == 0) {
dp[i] = Math.min(dp[i], dp[j] + i /j);
}
}
}
return dp[n];
}
}

③ LeetCode 10 正则表达式

解题思路

  • 设dp[i][j]为字符串s的前i个字符与字符串p的前j个字符能够匹配
  • 具体参考LeetCode

Java解答

class Solution {
public boolean isMatch(String s, String p) {
int n1=s.length();
int n2=p.length();
boolean[][] dp = new boolean[n1+1][n2+1];
for(int i=0;i<=n1;i++){
for(int j=0;j<=n2;j++){
if(j==0) dp[i][0]= i==0;
else{
if(p.charAt(j-1)!='*'){
if(i>0 && (s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.')){
dp[i][j]=dp[i-1][j-1];
}
}else{
if(j>1){
dp[i][j]|=dp[i][j-2];
}
if(i>0 && j>1 && (s.charAt(i-1)==p.charAt(j-2) || p.charAt(j-2)=='.')){
dp[i][j]|=dp[i-1][j];
}
}
}
}
}
return dp[n1][n2];
}
}

8、股票交易问题

① LeetCode 121 买卖股票的最佳时机

解题思路

  • 设dp[i]为前i天的最大收益，dp[i] = p[i] - minValue，其中minValue为前i-1个数中的最小值

Java解答

class Solution {
public int maxProfit (int[] prices) {
// write code here
if(prices == null || prices.length == 1) return 0;
int max = 0;
int min = prices[0];
for(int i = 0; i < prices.length; i++){
min = Math.min(min, prices[i]);
max = Math.max(max, prices[i]-min);
}
return max;
}
}

② LeetCode 188 买卖股票的最佳时机 IV

解题思路

  • 建立两个动态规划数组，buy[j]表示第j次买入时收益最大，sell[j]表示第j次卖出收益最大
  • 具体见LeetCode

Java解答

class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
k = Math.min(k, n / 2);
int[] buy = new int[k + 1];
int[] sell = new int[k + 1];
buy[0] = -prices[0];
sell[0] = 0;
for (int i = 1; i <= k; ++i) {
buy[i] = sell[i] = Integer.MIN_VALUE / 2;
}
for (int i = 1; i < n; ++i) {
buy[0] = Math.max(buy[0], sell[0] - prices[i]);
for (int j = 1; j <= k; ++j) {
buy[j] = Math.max(buy[j], sell[j] - prices[i]);
sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);
}
}
return Arrays.stream(sell).max().getAsInt();
}
}

③ LeetCode 309 最佳买卖股票时机含冷冻期

解题思路

  • f[i表示第i天结束之后的「累计最大收益」
    • 我们目前持有一支股票，对应的「累计最大收益」记为 f[i][0]；
    • 我们目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为 f[i][1]；
    • 我们目前不持有任何股票，并且不处于冷冻期中，对应的「累计最大收益」记为 f[i][2]。

Java解答

class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
// f[i][0]: 手上持有股票的最大收益
// f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
// f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
int[][] f = new int[n][3];
f[0][0] = -prices[0];
for (int i = 1; i < n; ++i) {
f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);
f[i][1] = f[i - 1][0] + prices[i];
f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);
}
return Math.max(f[n - 1][1], f[n - 1][2]);
}
}

最后

以上就是友好钢笔为你收集整理的（基于Java）算法笔记——动态规划算法的全部内容，希望文章能够帮你解决（基于Java）算法笔记——动态规划算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(51)

相关文章

LeetCode 剑指 Offer 65. 不用加减乘除做加法
LeetCode 剑指 Offer 65. 不用加减乘除做加法
leetcode 剑指Offer 65.不用加减乘除做加法 Java做题博客链接题目链接描述示例初始代码模板代码
leetcode 剑指Offer 65.不用加减乘除做加法 Java做题博客链接题目链接描述示例初始代码模板代码
剑指 Offer 65. 不用加减乘除做加法剑指 Offer 65. 不用加减乘除做加法
剑指 Offer 65. 不用加减乘除做加法剑指 Offer 65. 不用加减乘除做加法
两个class写在同一个java文件中
两个class写在同一个java文件中
（基于Java）算法笔记——动态规划算法
（基于Java）算法笔记——动态规划算法
java指令执行指定class文件目录1.首先配置好java环境2.找一个目录,写如下代码3.编译java文件4.运行
java指令执行指定class文件目录1.首先配置好java环境2.找一个目录,写如下代码3.编译java文件4.运行
剑指OfferII 002.二进制加法
剑指OfferII 002.二进制加法
java 错误: 找不到或无法加载主类 Solution.class
java 错误: 找不到或无法加载主类 Solution.class

评论列表共有 0 条评论

立即
投稿
返回
顶部