代码随想录算法训练营第45天

今日任务

● 70. 爬楼梯（进阶） ● 322. 零钱兑换 ● 279.完全平方数 ● 139.单词拆分

链接：https://docs.qq.com/doc/DUFVEbWRyZlpjaGty (opens in a new tab)

70. 爬楼梯（进阶版）

题解想法

其实是一个完全背包问题。

1阶，2阶，.... m阶就是物品，楼顶就是背包。

每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。

问跳到楼顶有几种方法其实就是问装满背包有几种方法。

这是背包里求排列问题，即：1、2 步和 2、1 步都是上三个台阶，但是这两种方法不一样！

所以需将背包放在外循环，将物品放在内循环。

import java.util.Scanner;
class climbStairs{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int m, n;
        while (sc.hasNextInt()) {
            // 从键盘输入参数，中间用空格隔开
            n = sc.nextInt();
            m = sc.nextInt();
 
            // 求排列问题，先遍历背包再遍历物品
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int j = 1; j <= n; j++) {
                for (int i = 1; i <= m; i++) {
                    if (j - i >= 0) dp[j] += dp[j - i];
                }
            }
            System.out.println(dp[n]);
        }
    }
}

322. 零钱兑换

自己想法

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, -1);
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (dp[j] > 0 && dp[j - coins[i]] > 0) dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                else if (dp[j] <= 0 && dp[j - coins[i]] > 0) dp[j] = dp[j - coins[i]] + 1;
                else {
                    if (j - coins[i] == 0) {
                        if (dp[j] < 0) dp[j] = 1;
                        else dp[j] = Math.min(dp[j], 1);
                    }
                }
            }
        }
        return dp[amount];
    }
}

优化了一下初始化方式和递推判断方式

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if (dp[amount] == Integer.MAX_VALUE) return -1;
        else return dp[amount];
    }
}

279.完全平方数

自己想法

完全背包，n是背包，平方数是物品。只是需要自己造物品

class Solution {
    private List<Integer> squares = new ArrayList<>();
    public int numSquares(int n) {
        squareListBuilder(n);
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < squares.size(); i++) {
            for (int j = squares.get(i); j <= n; j++) {
                if (dp[j - squares.get(i)] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - squares.get(i)] + 1);
                }
            }
        }
        return dp[n];
    }
 
    private void squareListBuilder(int n) {
        int i = 1;
        while (i * i <= n) {
            squares.add(i * i);
            i++;
        }
    }
}

单独建一次平方数列表太费时间，优化：

class Solution {
    private List<Integer> squares = new ArrayList<>();
    public int numSquares(int n) {
        // squareListBuilder(n);
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++) {
            for (int j = i * i; j <= n; j++) {
                if (dp[j - i * i] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                }
            }
        }
        return dp[n];
    }
 
    // private void squareListBuilder(int n) {
    //     int i = 1;
    //     while (i * i <= n) {
    //         squares.add(i * i);
    //         i++;
    //     }
    // }
}

139.单词拆分

自己想法

我将题目变为“单词拼接”，下面以“拼”为讲述逻辑，而不是“拆”。

完全背包问题，字符串是背包，单词字典是物品。

同时可以理解为是排列问题，例如字符串"aba"，单词字典b，那么“aba”只能由“a”、“b”、“a”拼出，而不能由“a”、“a”、“b”拼出。所以是排列。

因而背包放在外循环，物品放在内循环。

dp[i]表示字符串s的前i个字符能否由字典中的单词拼出。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int j =0; j <= s.length(); j++) {
            for (int i = 0; i < wordDict.size(); i++) {
                // 递推判断条件：都满足时，才能递推dp[j] = true;
                // 1. 确保不越界：j - wordDict.get(i).length() >= 0
                // 2. 前面的字符串是可以拼出来的：dp[j - wordDict.get(i).length()]
                // 3. 当前查看的单词是否和字符串s从start_index开始的一段匹配：checkWord(s, wordDict.get(i), j - wordDict.get(i).length())
                if (j - wordDict.get(i).length() >= 0 &&
                dp[j - wordDict.get(i).length()] && 
                checkWord(s, wordDict.get(i), j - wordDict.get(i).length())) dp[j] = true;
            }
        }
        return dp[s.length()];
    }
    // 判断当前查看的单词是否和字符串s从start_index开始的一段匹配
    private boolean checkWord(String s, String word, int start_index) {
        for (int i = 0; i < word.length(); i++) {
            if (i + start_index >= s.length() || i + start_index < 0) return false;
            if (s.charAt(i + start_index) != word.charAt(i)) return false;
        }
        return true;
    }
}