动态规划编程题集合（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。

引用官方图片

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];    }}作者：LeetCode-Solution链接：https://leetcode.cn/problems/integer-break/solution/zheng-shu-chai-fen-by-leetcode-solution/来源：力扣（LeetCode）