leetcode 474.一和零

1. 思路

把总共的0和1的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用0-1背包问题的思路完成，这里的目标值是能放进背包的字符串的数量。
动态规划的思路是:物品一个一个尝试，容量一点一点尝试，每个物品分类讨论的标准是:选与不选。
定义状态：表示输入字符串在子区间能够使用个0和个l的字符串的最大数量
状态转移方程：
初始化：为了避免分类讨论，通常多设置一行。这里可以认为，第 0 个字符串是空串。第 0 行默认初始化为 0。
输出：输出是最后一个状态，即：

2. 代码

public class FindMaxForm1 {
    public int findMaxForm(String[] strs, int m, int n) {
        int length = strs.length;
        int[][][] dp = new int[length+1][m+1][n+1];
        for(int i=1;i<=length;i++){
            int[] zerosOnes = getZerosOnes(strs[i-1]);
            int zeros = zerosOnes[0],ones = zerosOnes[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>=zeros&&k>=ones){
                        dp[i][j][k] = Math.max(dp[i][j][k],dp[i-1][j-zeros][k-ones]+1);
                    }
                }
            }
        }
        return dp[length][m][n];
    }
    public int[] getZerosOnes(String str){
        int[] zerosOnes = new int[2];
        int length = str.length();
        for(int i=0;i<length;i++){
            zerosOnes[str.charAt(i)-'0']++;
        }
        return zerosOnes;
    }
    public static void main(String[] args) {
        System.out.println(new FindMaxForm1().findMaxForm(new String[]{"10", "0001", "111001", "1", "0"},5,3));
    }
}

Leetcode 1049.最后一块石头的重量II

1. 思路

问题转换彻底切换为01背包问题：从stones数组中选择,凑成总和不超过的最大价值。定义代表考虑前个物品(数值)，凑成不超过的最大价值。
转移方程：

2. 代码

    //01背包问题
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int stone:stones){
                sum+=stone;
        }
        int target = sum/2;
        int[] packages = new int[target+1];
        for(int i=0;i<stones.length;i++){
            int cur = stones[i];
            for(int j = cur;j<=target;j++){
                packages[j] = Math.max(packages[j],packages[j-cur]+cur);
            }
        }
        return sum-packages[target]*2;
    }

Leetcode 518.零钱兑换

1. 思路

通过动态规划的方法计算可能的组合数。用表示金额之和等于的硬币组合数，目标是求。动态规划的边界是。不选取任何硬币时，金额之和为0，因此只有1种硬币组合。
对于面额为的硬币当时，如果存在一种硬币组合的金额之和等于,则在该硬币组合中增加一个面额为的硬币，即可得到一种金额之和等于i的硬币组合。因此需要遍历,对于其中的每一种面额的硬币，更新数组dp 大于等于该面额的元素的值。
由此可以得到初始动态规划的做法：

• 初始化
• 遍历,对于其中的每个元素coin，进行如下操作：
  • 遍历i从coin到amount,将的值加到

• 最终得到的值

  2. 代码

  class Solution {
          public int change(int cnt, int[] cs) {
            int n = cs.length;
            int[] f = new int[cnt + 1];
            f[0] = 1;
            for (int i = 1; i <= n; i++) {
                int val = cs[i - 1];
                for (int j = val; j <= cnt; j++) {
                    f[j] += f[j - val];
                }
            }
            return f[cnt];
        }
  }

  Leetcode 279.完全平方数

  1. 思路

• 1. 思路
• 首先初始化长度为的数组,每个位置都为0
• 如果n为0,则结果为0
• 对数组进行遍历，下标为,每次都将当前数字先更新为最大的结果，即，比如，最坏结果为4=1+1+1+1 即为4个数字
• 动态转移方程：表示当前数字，j*j表示平方数
• 时间复杂度:,sqrt为平方根

  2. 代码

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