139.单词拆分

• 刷题https://leetcode.cn/problems/word-break/description/
• 文章讲解https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html
• 视频讲解https://www.bilibili.com/video/BV1pd4y147Rh/?vd_source=af4853e80f89e28094a5fe1e220d9062

• 题解：

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] valid = new boolean[s.length() + 1];
        valid[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i && !valid[i]; j++) {
                if (set.contains(s.substring(j, i)) && valid[j]) {
                    valid[i] = true;
                }
            }
        }

        return valid[s.length()];
    }
}

56. 携带矿石资源（第八期模拟笔试）

• 刷题https://kamacoder.com/problempage.php?pid=1066
• 文章讲解https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85.html

• 题解：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt();
        int n = sc.nextInt();
        int[] weight = new int[n];
        int[] value = new int[n];
        int[] numbers = new int[n];
        
        for (int i = 0;i < n;i++) {
            weight[i] = sc.nextInt();
        }
        for (int i = 0;i < n;i++) {
            value[i] = sc.nextInt();
        }
        for (int i = 0;i < n;i++) {
            numbers[i] = sc.nextInt();
        }
        
        int[] dp = new int[c+1];
        for (int i = 0;i < n;i++) {
            for (int j = c;j >= weight[i];j--) {
                for (int k = 1;k <= numbers[i] && (j - k * weight[i]) >= 0;k++) {
                    dp[j] = Math.max(dp[j],dp[j-weight[i] * k]+ k * value[i]);
                }
            }
        }
        System.out.println(dp[c]);
    }
}