代码随想录刷题|LeetCode 70. 爬楼梯(进阶) 322. 零钱兑换 279.完全平方数 139.单词拆分

简介: 代码随想录刷题|LeetCode 70. 爬楼梯(进阶) 322. 零钱兑换 279.完全平方数 139.单词拆分

70. 爬楼梯 (进阶)

题目链接:力扣

思路


在使用动态规划解决爬楼梯问题的时候,从到达一个台阶有多少种方式入手,使用动态规划是可以很好的解决


       学了完全背包后,可以从另一个角度分析这道题目

       物品:每次可以爬1个台阶、每次可以爬2个台阶

       拿取:可以重复拿取步数

       背包:n阶台阶数

       求值:求的是有多少种方法爬到楼顶(排列数)


       这样看起来,这个题目的内容就和求排列数一样了

       和 377. 组合总和Ⅳ  一样了


       求排列数的注意内容:

       1、初始化dp[0] = 1

       2、遍历时,先遍历背包,再遍历物品

       3、递推公式为 dp[j] = dp[j-weigth[i]]


多步爬楼梯问题:

假设你正在爬楼梯,需要跨过m个台阶才能到达楼顶。每一步你可以跨过1个台阶、2个台阶、3个台阶……m个台阶,直到n层台阶,你有多少种方法可以爬到楼顶呢

多部爬楼梯解决:

按照上面的思路,如果每次爬楼梯的步数是 1 或者 2,那么物品的数组就是【1,2】

如果每次爬楼梯的步数是 1、2、3……m,那么物品的数组就是【1,2,3……m】


爬楼梯

1或2步爬楼梯

// 创建步数数组
class Solution {
    public int climbStairs(int n) {
        // 物品数组
        int[] nums = new int[]{1,2};
        // 创建dp数组
        int[] dp = new int[n+1];
        // 初始化dp数组
        dp[0] = 1;
        // 填充dp数组
        for (int j = 1; j <= n; j++) {
            for (int i = 0; i < nums.length; i++) {
                if (j >= nums[i]) {
                    dp[j] += dp[j-nums[i]];
                }
            }
        }
        return dp[n];
    }
}
// 不创建步数数组
class Solution {
    public int climbStairs(int n) {
        // 创建dp数组
        int[] dp = new int[n+1];
        // 初始化dp数组
        dp[0] = 1;
        // 填充dp数组
        for (int j = 1; j <= n; j++) {
            for (int i = 1; i <= 2; i++) {
                if (j >= i) {
                    dp[j] += dp[j-i];
                }
            }
        }
        return dp[n];
    }
}

多步爬楼梯

class Solution {
    public int climbStairs(int n) {
        // 创建dp数组
        int[] dp = new int[n+1];
        // 初始化dp数组
        dp[0] = 1;
        // 填充dp数组
        for (int j = 1; j <= n; j++) { // 遍历背包
            for (int i = 1; i <= m; i++) { // 遍历步数,步数是从1开始的
                if (j >= i) {
                    dp[j] += dp[j-i];
                }
            }
        }
        return dp[n];
    }
}

322. 零钱兑换

题目链接:力扣

思考


虽然已经做了几天的动态规划,但是每次再拿到动态规划的题目的时候思路还不是很清楚,主要就是如何定义dp[]数组,定义了dp[]数组之后怎么确定递推公式,确定了递推公式之后怎么对数组进行初始化,初始化之后使用那种遍历顺序


       目前来说,定义dp[]数组,基本上都是题目要求什么就定义什么。主要有三类:

       1、纯求背包中物品的价值:

               这种就是一般的背包问题,是比较简单的一种

               递推公式一般是:dp[ j ] = max(dp[ j ],dp[ j - weigth[ i ] ] + value[ i ]);

       2、求物品装满背包的方法数

               这种dp[]数组就是方法数,如果是完全背包,还可能牵扯组合数和排列数

               递归公式一般是:dp[ j ] += dp[ j - weight[ i ] ]

               由于方法数是逐步积累的,所以初始化应该是dp[ 0 ] = 1

       3、求装满背包时,背包中的物品数

               这种dp[]数组求得是最终背包中的物品个数

               递推公式一般与dp[ j - weight[ i ] ] + 1 ) 有关

               如果是求最大个数:就是dp[ j ] = max(dp[ j ],dp[ j - weight[ i ] ] + 1 );由于是求最大值,初始化时dp[0] = 0,其余的也为0。对应的题目有 474.一和零

               如果是求最小个数:就是dp[ j ] = min(dp[ j ],dp[ j - weight[ i ] ] + 1 );由于是求最小值,初始化时dp[0] = 0,其余的为MAX_VALUE。对应的题目有 322.零钱兑换


下面对本题目进行动态五部曲的分析:


1、确定dp数组及其含义

       题目求什么,就定义什么。题目要求的内容:计算并返回可以凑成总金额所需的 最少的硬币个数


       dp[ j ]: 凑成总金额为 j 所需要硬币的最小个数


2、确定递推公式

       确定好递推公式后,发现这是上面总结的第三类问题,是求背包中的物品个数,也就是和dp[ j - coins[ i ] ] + 1 ) 有关


       如果说添加了当前物品(coins[i]),那么这个背包中的物品就需要进行添加,背包中的物品个数就是 dp[ j - coins[i] ] + 1

       如果说没有添加当前物品(coins[i]), 那么这个背包中的物品中的个数就不需要进行改变,背包中物品的个数就是 dp[ j ]

       所以说dp[ j ] = min(dp[ j ],dp[ j - coins[ i ] ] + 1 )


3、初始化dp数组

       凑足总金额为0 所需要硬币的个数一定是0,所以dp[0] = 0


       其余的下标的元素必须初始化为一个最大值,否则 min(dp[ j ],dp[ j - coins[ i ] ] + 1 ) 计算出的值就被初始化的值覆盖掉了


4、确定遍历顺序

       不强调组合和排列,先遍历背包或者先遍历物品都是可以的


零钱兑换

先遍历物品,再遍历背包


class Solution {
    public int coinChange(int[] coins, int amount) {
        // 创建dp数组
        int[] dp = new int[amount + 1];
        // 初始化dp数组
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        // 遍历更新dp数组
        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);
                }             
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

先遍历背包,再遍历物品

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 创建dp数组
        int[] dp = new int[amount + 1];
        // 初始化dp数组
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        // 遍历更新dp数组
        for (int j = 0; j <= amount; j++) {  // 再遍历背包
            for (int i = 0; i < coins.length; i++) { // 先遍历物品
                if (j - coins[i] >=0 && dp[j-coins[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j],dp[j-coins[i]] + 1);
                }             
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

279.完全平方数

题目链接:力扣

思路

       这道题和上面322.零钱兑换是一样的,只不过这道题目的物品数组没有明给,需要自己创建,说着直接套用到公式中

完全平方数

创建完全平方和数组,套用公式

class Solution {
    public int numSquares(int n) {
        // 首先要根据背包创建完全平方和数组
        // 对 n 进行开平方
        double lens = Math.sqrt(n);
        // 对开方出来的数组进行向上取整
        int len = (int)Math.ceil(lens);
        // 创建物品数组
        int[] nums = new int[len + 1]; // 遍历的时候从下标1开始
        for (int i = 0; i <= len; i++) {
            nums[i] = i * i;
        }
        // 创建dp数组
        int[] dp = new int[n + 1];
        // 初始化dp数组
        dp[0] = 0; // 和为0的完全平方数的最少数量是0
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE; //设置最大值,避免被覆盖
        }
        // 遍历更新dp数组
        for (int i = 1; i <= len; i++) {
            for (int j = nums[i]; j <= n; j++) {
                if (dp[j-nums[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j],dp[j-nums[i]] + 1);
                }
            }
        }
        return dp[n];
    }
}

将完全平方和融入到公式中

class Solution {
    public int numSquares(int n) {
        // 创建dp数组
        int[] dp = new int[n + 1];
        // 初始化dp数组
        dp[0] = 0; // 和为0的完全平方数的最少数量是0
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE; //设置最大值,避免被覆盖
        }
        // 遍历更新dp数组
        for (int i = 1; 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];
    }
}

139.单词拆分

题目链接:力扣

思路


比较直接的想法就是使用回溯法不断去组合字符串,比较组合出来的字符串是否与目标字符串相同,显然,回溯这种枚举的方法有很多无效功


       将目标字符串看成背包,将集合中的单词看成物品,集合中的单词能不能组成目标字符串,就是问物品能不能把背包装满。集合中的字符串是可以重复使用的,说明这是一个完全背包问题


1、确定dp数组的含义

dp[i]:字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词


2、确定递推公式

i 是在遍历目标字符串

j 是每次从0开始遍历目标字符串


对于leetcode, i 遍历到4的时候,j 再对字符串从0遍历,判断s.substring(0,4) -- “leet”在 集合中是存在的,并且dp[0]是为true的,所以此时 下标4 位置上就可以设置为 true,代表leet 是存在在集合中的

下一次,i遍历到8的时候,j 再对字符串从0开始遍历,遍历到 j = 4的时候,判断s.substring(4,8) --"code" 在集合中是存在的,并且dp[4]是为true的,所以此时下标8位置上就可以设置成true,代表 code是存在在集合中的


其实本质上就是使用 true 对字符串进行了分割,如果分割到最后也是true,那就说明这个字符串是可以由集合中的元素组成的


所以判断该元素在集合中存在的条件是 set.contains(s.substring(j,i)) && dp[j]


3、dp数组如何初始化

从递归公式中可以看出,dp[i] 的状态依靠 dp[j]是否为true,那么dp[0]就是递归的根基,dp[0]一定要为true,否则递归下去后面都都是false了


4、确定遍历顺序

本题使用外层for循环遍历物品,内层for遍历背包或者外层for遍历背包,内层for循环遍历物品都是可以的


但本题还有特殊性,因为是要求子串,最好是遍历背包放在外循环,将遍历物品放在内循环


5、打印dp数组


a28651afe9ff4ed3bce4b1af24063188.png


单词拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        // 创建dp数组
        boolean[] dp = new boolean[s.length() + 1];
        // 初始化dp数组
        dp[0] = true;
        // 遍历填充dp数组
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i && !dp[i]; j++) {
                if (set.contains(s.substring(j,i)) && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}
相关文章
|
2月前
Leetcode(最后一个单词长度)
这篇文章介绍了两种解决LeetCode第58题的方法,即计算给定字符串中最后一个单词的长度,方法包括翻转字符串和逆向遍历统计。
20 0
|
2月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
19 0
|
4月前
|
算法
LeetCode第58题最后一个单词的长度
LeetCode第58题"最后一个单词的长度"的解题方法,通过从字符串末尾向前遍历并计数非空格字符,直接得出最后一个单词的长度。
LeetCode第58题最后一个单词的长度
|
4月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
46 4
|
4月前
|
Python
【Leetcode刷题Python】生词本单词整理
文章提供了一个Python程序,用于帮助用户整理和排版生词本上的单词,包括去除重复单词、按字典序排序,并按照特定的格式要求进行打印排版。
42 3
|
4月前
|
Python
【Leetcode刷题Python】343. 整数拆分
LeetCode 343题 "整数拆分" 的Python解决方案,使用动态规划算法来最大化正整数拆分为多个正整数之和的乘积。
27 0
|
4月前
|
Python
【Leetcode刷题Python】318. 最大单词长度乘积
本文提供了LeetCode题目318的Python编程解决方案,题目要求在一个字符串数组中找出两个不含有公共字母的单词,且这两个单词的长度乘积最大,如果不存在这样的两个单词,则返回0。
21 0
【超直白】leetcode 279 完全平方数
【超直白】leetcode 279 完全平方数
|
6月前
力扣-2029-石子游戏-‘屎山’代码
力扣-2029-石子游戏-‘屎山’代码
44 3
|
6月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)