动态规划编程题集合(leetcode)

简介: 动态规划编程题集合(leetcode)

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

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

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

输入:coins = [1, 2, 5], amount = 11输出:3解释:11 = 5 + 5 + 1
  public int coinChange(int[] arr, int sum) {
         int[] f=new int[sum+1];
        f[0]=0;
        for(int i=1;i<f.length;i++){
            f[i]=Integer.MAX_VALUE;
            for(int j=0;j<arr.length;j++){
                if(i>=arr[j]&&f[i-arr[j]]!=Integer.MAX_VALUE){
                    f[i]=Math.min(f[i],f[i-arr[j]]+1);
                }
            }
        }
        if(f[sum]==Integer.MAX_VALUE)
            f[sum]=-1;
        return f[sum];
    }

二维背包问题解法

 //dp[i][j] i表示数组前i个钱数,j表示金币总金额,二维数组在这里其实是完全背包问题,状态转移方程为
//      if(j>=arr[i-1]&&dp[i][j-arr[i-1]]!=Integer.MAX_VALUE)
//    dp[i][j]=Math.min(dp[i][j-arr[i-1]]+1,dp[i-1][j]);
//                else
//    dp[i][j]=dp[i-1][j];
    //由于是求最小的硬币个数,所以初始化一开始全为最大值,注意当总额为0的时候,要初始化为0
    public static int coinChange(int[] arr, int sum) {
        int[][] dp=new int[arr.length+1][sum+1];
        for(int i=1;i<=arr.length;i++){
            for(int j=1;j<=sum;j++)
                dp[i][j]=Integer.MAX_VALUE;
        }
        for(int i=0;i<=arr.length;i++)
            dp[i][0]=0;
        for(int i=0;i<=sum;i++)
            dp[0][i]=Integer.MAX_VALUE;
        for(int i=1;i<=arr.length;i++){
            for(int j=1;j<=sum;j++){
                if(j>=arr[i-1]&&dp[i][j-arr[i-1]]!=Integer.MAX_VALUE)
                    dp[i][j]=Math.min(dp[i][j-arr[i-1]]+1,dp[i-1][j]);
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        return dp[arr.length][sum]==Integer.MAX_VALUE?-1:dp[arr.length][sum];
    }

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

输入:n = 12输出:3 
解释:12 = 4 + 4 + 4
public int numSquares(int n) {
        int[] f=new int[n+1];
        f[0]=0;
        for(int i=1;i<f.length;i++){
            f[i]=Integer.MAX_VALUE;
            for(int j=1;j<=Math.sqrt(i);j++){
                if(j*j<=i&&f[i-j*j]!=Integer.MAX_VALUE){
                    f[i]=Math.min(f[i],f[i-j*j]+1);
                }
            }
        }
        return f[n];
    }

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。


输入: s = "leetcode", wordDict = ["leet", "code"]

输出: true

解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

dp[i]表示可以s字符串从0到i的子串可以利用字典中出现的单词拼接

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

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的 二叉搜索树的种数。

    private  int com(int n) {
       int[] f=new int[n+1];
       f[0]=1;
       f[1]=1;
       for(int i=2;i<=n;i++){
           for(int j=1;j<=i;j++){
               f[i]+=f[j-1]*f[i-j];
           }
       }
       return f[n];
    }
给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。返回 你可以获得的最大乘积

输入: n = 2

输出: 1

解释: 2 = 1 + 1, 1 × 1 = 1。

引用官方图片

995eb0f5e7e9cfc7758fe797afb491dc.png

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
}
相关文章
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer II 082. 含有重复元素集合的组合
解决LeetCode平台《剑指 Offer II 082. 含有重复元素集合的组合》题目的Python代码实现,通过深度优先搜索算法找出所有和为特定目标值的数字组合,并在搜索过程中通过排序和跳过重复元素来避免解集中出现重复组合。
43 2
|
6月前
|
缓存
力扣每日一题 6/14 动态规划+数组
力扣每日一题 6/14 动态规划+数组
41 1
|
6月前
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
55 0
|
6月前
|
存储
力扣每日一题 6/19 排序+动态规划
力扣每日一题 6/19 排序+动态规划
35 0
|
6月前
|
算法
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
48 0
|
6月前
|
机器人
【LeetCode】--- 动态规划 集训(二)
【LeetCode】--- 动态规划 集训(二)
45 0
|
6月前
【LeetCode】--- 动态规划 集训(一)
【LeetCode】--- 动态规划 集训(一)
37 0
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
63 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
125 2