手机免费建站平台下载,网站源码上传到哪个文件夹,手机制作动画软件app免费,培训教育网站开发代码随想录训练营二刷第四十七天 | 70. 爬楼梯 #xff08;进阶#xff09; 322. 零钱兑换 279.完全平方数
一、70. 爬楼梯 #xff08;进阶#xff09;
题目链接#xff1a;https://leetcode.cn/problems/climbing-stairs/ 思路#xff1a;物品是楼梯1和2#xff0c;…代码随想录训练营二刷第四十七天 | 70. 爬楼梯 进阶 322. 零钱兑换 279.完全平方数
一、70. 爬楼梯 进阶
题目链接https://leetcode.cn/problems/climbing-stairs/ 思路物品是楼梯1和2背包是n求排列数背包在外物品在内递推公式dp[i] dp[i - j]
class Solution {public int climbStairs(int n) {int[] dp new int[n1];dp[0] 1;for (int i 0; i n; i) {for (int j 1; j 2; j) {if (j i) {dp[i] dp[i - j];}}}return dp[n];}
}二、322. 零钱兑换
题目链接https://leetcode.cn/problems/coin-change/ 思路求所需物品的最少数量完全背包定义dp[i]表示背包容量为i时所需物品的最少数量递推公式dp[i] dp[i-j] 1。自然等于放这个物品的前一个位置加1。如dp[5] dp[5 - 1] 1 或者 dp [5 - 2] 1等等一定得是这些当中最少的那个。故dp[j] Math.min(dp[j], dp[j-coins[i]] 1)。最少数量无关排列或者组合。初始化为最大值dp[0]0另外必须得是dp[j-coins[i]] ! max时才能进行递推如果dp[j-coins[i]] max说明前一个数就没用现在当前不能在没使用的基础上进行递推。
class Solution {public int coinChange(int[] coins, int amount) {int[] dp new int[amount1];int max Integer.MAX_VALUE;for (int i 1; i dp.length; i) {dp[i] max;}for (int i 0; i coins.length; i) {for (int j coins[i]; j amount; j) {if (dp[j-coins[i]] ! max) {dp[j] Math.min(dp[j], dp[j-coins[i]] 1);}}}return dp[amount] max ? -1 : dp[amount];}
}三、279.完全平方数
题目链接https://leetcode.cn/problems/perfect-squares/ 思路和上题基本一样细节在于完全平方数为i*i
class Solution {public int numSquares(int n) {int[] dp new int[n1];int max Integer.MAX_VALUE;for (int i 1; i dp.length; i) {dp[i] max;}for (int i 1; i*i n; i) {for (int j i*i; j n; j) {dp[j] Math.min(dp[j], dp[j - i*i] 1);}}return dp[n];}
}
