res = new ArrayList<>(); public List g_class solution { public int rob(">
devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

动态规划---例题详解篇（入门-深入）_class solution { public int rob(int[] nums) { int

作者：IT小白 | 2024-05-05 07:01:16

赞

踩

class solution { public int rob(int[] nums) { int len = nums.length; if(len

1.数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]

  1. class Solution {
  2.  
  3.     public List<String> res = new ArrayList<>();
  4.  
  5.     public List<String> generateParenthesis(int n) {
  6.  
  7.         dfs(0,0,n,"");
  8.         return res;
  9.     }
  10.  
  11.     public void dfs(int leftCount,int rightCount,int n,String sum) {
  12.  
  13.         
  14.         if(leftCount > n || rightCount > n || rightCount > leftCount)
  15.         return;
  16.  
  17.         if(leftCount == n && rightCount == n) {
  18.  
  19.             res.add(sum);
  20.             return;
  21.         }
  22.         
  23.         dfs(leftCount+1,rightCount,n,sum+"(");
  24.         dfs(leftCount,rightCount + 1,n,sum + ")");
  25.     }
  26. }

2.给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
注意：a + b 意味着字符串 a 和 b 连接。

 （1）使用二维数组

  1. class Solution {
  2.     public boolean isInterleave(String s1, String s2, String s3) {
  3.  
  4.         int n = s1.length();
  5.         int m = s2.length();
  6.         int p = s3.length();
  7.  
  8.         if(n + m != p)
  9.         return false;
  10.  
  11.         //f[i][j]表示用s1的前i个字符和用s2的前i个字符是否能符合s3的前(i + j - 1)个字符
  12.         boolean[][] f = new boolean[n + 1][m + 1];
  13.         f[0][0] = true;
  14.  
  15.         for(int i = 0;i <= n;i++) {
  16.  
  17.             for(int j = 0;j <= m;j++) {
  18.  
  19.                 int q = i + j - 1;
  20.                 if(i > 0) {
  21.  
  22.                     //f[i][j] = f[i][j] || (f[i - 1][j] && s3.charAt(q) == s1.charAt(i - 1));
  23.                     //原题是以上的形式，速度慢了一半
  24.                     //这里的f[i][j] = f[i][j]只是因为j要从0开始，告诉j我i能满足，已经不需要你了
  25.                     
  26.                     f[i][j] = (f[i - 1][j] && s3.charAt(q) == s1.charAt(i - 1));
  27.                 }
  28.  
  29.                 if(j > 0) {
  30.                     f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(q));
  31.                 }
  32.             }
  33.         }
  34.  
  35.         return f[n][m];
  36.     }
  37. }

(2)使用一维数组进行优化

  1. class Solution {
  2.     public boolean isInterleave(String s1, String s2, String s3) {
  3.         int n = s1.length(), m = s2.length(), t = s3.length();
  4.  
  5.         if (n + m != t) {
  6.             return false;
  7.         }
  8.  
  9.         boolean[] f = new boolean[m + 1];
  10.  
  11.         f[0] = true;
  12.         for (int i = 0; i <= n; ++i) {
  13.             for (int j = 0; j <= m; ++j) {
  14.                 int p = i + j - 1;
  15.                 if (i > 0) {
  16.                     f[j] = f[j] && s1.charAt(i - 1) == s3.charAt(p);
  17.                 }
  18.                 if (j > 0) {
  19.                     f[j] = f[j] || (f[j - 1] && s2.charAt(j - 1) == s3.charAt(p));
  20.                 }
  21.             }
  22.         }
  23.  
  24.         return f[m];
  25.     }
  26. }

(3)动态规划模板

  1. class Solution {
  2.     public boolean isInterleave(String s1, String s2, String s3) {
  3.  
  4.         if(s1 == null || s2 == null || s3 == null)
  5.         return false;
  6.  
  7.         char[] a = s1.toCharArray();
  8.         char[] b = s2.toCharArray();
  9.         char[] c = s3.toCharArray();
  10.  
  11.         if(s1.length() + s2.length() != s3.length())
  12.         return false;
  13.  
  14.         boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
  15.         dp[0][0] = true;
  16.  
  17.         for(int i = 1;i <= s1.length();i++) {
  18.  
  19.             if(s1.charAt(i - 1) != s3.charAt(i - 1))
  20.             break;
  21.  
  22.             dp[i][0] = true;
  23.         }
  24.  
  25.         for(int i = 1;i <= s2.length();i++) {
  26.  
  27.             if(s2.charAt(i - 1) != s3.charAt(i - 1))
  28.             break;
  29.  
  30.             dp[0][i] = true;
  31.         }
  32.  
  33.  
  34.         for(int i = 1;i <= s1.length();i++) {
  35.  
  36.             for(int j = 1;j <= s2.length();j++) {
  37.  
  38.                 if((a[i - 1] == c[i + j - 1] && dp[i -1][j]) || (b[j - 1] == c[i + j - 1] && dp[i][j - 1])) {
  39.  
  40.                     dp[i][j] = true;
  41.                 }
  42.             }
  43.         }
  44.  
  45.         return dp[s1.length()][s2.length()];
  46.     }
  47. }

3.

  1. class Solution {
  2.     public int maximalSquare(char[][] matrix) {
  3.  
  4.         int n = matrix.length,m = matrix[0].length;
  5.         int max = 0;
  6.         if(matrix == null || n == 0 || m == 0)
  7.         return 0;
  8.  
  9.         //dp[i][j]记录的是以i，j为正方形的右下方坐标
  10.         int[][] dp = new int[n][m];
  11.  
  12.         for(int i = 0;i < n;i++) {
  13.  
  14.             for(int j = 0;j < m;j++) {
  15.  
  16.                 if(matrix[i][j] == '1') {
  17.  
  18.                     if(i == 0 || j == 0) {
  19.  
  20.                         dp[i][j] = 1;
  21.                     }else {
  22.  
  23.                         //这里取最小值是因为比如i，j的左边有一个一，上面也有一个一，但是斜上是0，这样是不能构成正方形的，所以应该取最小值
  24.                         dp[i][j] = Math.min(Math.min(dp[i - 1][j],dp[i][j - 1]),dp[i - 1][j - 1]) + 1;
  25.                     }
  26.  
  27.                     max = Math.max(max,dp[i][j]);
  28.                 }
  29.             }
  30.         }
  31.  
  32.         return max * max;
  33.     }
  34. }
  35.  
  36. 作者：fff999
  37. 链接：https://leetcode-cn.com/problems/maximal-square/solution/by-fff999-buj0/
  38. 来源：力扣（LeetCode）
  39. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法2（但是会超时dfs）

  1. class Solution {
  2.  
  3.     int n,m;
  4.     public int maximalSquare(char[][] matrix) {
  5.  
  6.         int max = 0;
  7.         n = matrix.length;
  8.         m = matrix[0].length;
  9.  
  10.         if(matrix == null || n == 0 || m == 0)
  11.         return 0;
  12.  
  13.         for(int i = 0;i < n;i++) {
  14.  
  15.             for(int j = 0;j < m;j++) {
  16.  
  17.                 if(matrix[i][j] == '1') {
  18.  
  19.                     max = Math.max(max,dfs(i,j,matrix));
  20.                 }
  21.             }
  22.         }
  23.  
  24.         return max * max;
  25.     }
  26.  
  27.     public int dfs(int i,int j,char[][] matrix) {
  28.  
  29.         if(i < 0 || j < 0 || i >= n || j >= m) {
  30.  
  31.             return 0;
  32.         }
  33.  
  34.         if(matrix[i][j] != '1')
  35.         return 0;
  36.  
  37.         int res = 1;
  38.         int a = dfs(i + 1,j,matrix);
  39.         int b = dfs(i,j + 1,matrix);
  40.         int c = dfs(i + 1,j + 1,matrix);
  41.  
  42.         res += Math.min(Math.min(a,b),c);
  43.  
  44.         return res;
  45.     }
  46. }

4.

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.  
  4.         int len = nums.length;
  5.  
  6.         if(len == 1)
  7.         return nums[0];
  8.  
  9.         int[] dp = new int[len];
  10.  
  11.         dp[0] = nums[0];
  12.         dp[1] = Math.max(nums[0],nums[1]);
  13.  
  14.         for(int i = 2;i < len;i++) {
  15.  
  16.             dp[i] = Math.max(dp[i - 2] + nums[i],dp[i-1]);
  17.         }
  18.  
  19.         return dp[len - 1];
  20.     }
  21. }

5.

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：

输入：nums = [1,2,3]
输出：3

  1. class Solution {
  2.  
  3. //其实就是分成两种情况，每种情况的起始与结束的下标不同
  4.     public int rob(int[] nums) {
  5.  
  6.         int len = nums.length;
  7.         if(len == 1)
  8.         return nums[0];
  9.         else if(len == 2) {
  10.             return Math.max(nums[0],nums[1]);
  11.         }
  12.         int[] dp1 = new int[len];
  13.         int[] dp2 = new int[len];
  14.          
  15.         dp1[0] = nums[0];
  16.         dp1[1] = Math.max(nums[0],nums[1]);
  17.  
  18.         for(int i = 2;i < len - 1;i++) {
  19.  
  20.             dp1[i] = Math.max(dp1[i - 2] + nums[i],dp1[i - 1]);
  21.         }
  22.  
  23.         dp2[1] = nums[1];
  24.         dp2[2] = Math.max(nums[2],nums[1]);
  25.  
  26.         for(int i = 3;i < len;i++) {
  27.  
  28.             dp2[i] = Math.max(dp2[i - 2] + nums[i],dp2[i - 1]);
  29.         }
  30.  
  31.         return Math.max(dp1[len - 1-1],dp2[len - 1]);
  32.     }
  33. }

6.

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public int rob(TreeNode root) {
  18.  
  19.         HashMap<TreeNode,Integer> map = new HashMap<>();
  20.         return dp(root,map);
  21.     }
  22.  
  23.     public int dp(TreeNode root,HashMap<TreeNode,Integer> map) {
  24.  
  25.         if(root == null)
  26.         return 0;
  27.  
  28.         if(map.containsKey(root))
  29.         return map.get(root);
  30.  
  31.         int val = root.val;
  32.  
  33.         if(root.left != null) {
  34.  
  35.             val += dp(root.left.right,map) + dp(root.left.left,map);
  36.         }
  37.  
  38.         if(root.right != null) {
  39.  
  40.             val += dp(root.right.left,map) + dp(root.right.right,map);
  41.         }
  42.  
  43.         
  44.  
  45.         int res =  Math.max(val,dp(root.left,map) + dp(root.right,map));
  46.  
  47.         map.put(root,res);
  48.  
  49.         return res;
  50.     }
  51. }

7.

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int[] dp = new int[amount + 1];
  4.         int max = amount + 1;
  5.         Arrays.fill(dp,max);
  6.         dp[0] = 0;
  7.  
  8.         for(int i = 1;i <= amount;i++) {
  9.  
  10.             for(int j = 0;j < coins.length;j++) {
  11.  
  12.                 if(i - coins[j] >= 0) {
  13.  
  14.                     dp[i] = Math.min(dp[i],dp[i - coins[j]] + 1);
  15.                 }
  16.             }
  17.         }
  18.  
  19.         return dp[amount] > amount ? -1 : dp[amount];
  20.     }
  21. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/537741
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。