LeetCode 322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

题目大意:你有一些不同面值的硬币,你需要用这些硬币凑成amount值,计算需要的最少的硬币个数~如果不能凑成,就返回-1

分析:设立dp数组(dp[i]表示凑成i需要的最小硬币个数),一开始dp[0]等于0,i从1到amount填充dp[i]的值,第二层循环遍历coins数组,假设coins[j]作为第一个硬币,那么dp[i-coins[j]]表示剩下的金额需要的硬币个数,此时判断i-coins[j]是否等于-1,也就是是否能够凑成,如果能够凑成,那么当dp[i]>0时表示凑成i需要dp[i]个硬币,这种情况下如果dp[i-coins[j]]+1更小,就更新dp[i],否则就保留dp[i]的值。如果dp[i]本身就<=0说明前面没有方法可以凑成i,那么就直接更新dp[i]为dp[i-coins[j]] + 1的值,有一种凑成的方法总比没有好~最后返回dp[amount]的值表示凑成amount数量需要的最小硬币个数,如果不存在,本身dp数组的初值就为-1,所以也会按照要求返回-1~

 

LeetCode 377. Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.
Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

题目大意:给一个数组,都是正整数且没有重复的数字,任取里面的数字,问有多少种相加等于target的方式
分析:建立dp数组,(dp[i]表示相加等于i的方法有dp[i]个)设dp[0]等于1。i从1到target,给dp[i]赋值。要想知道dp[i]的值,用j遍历nums数组,只要将dp[i-nums[j]]的值累加即可得到,注意只累加i大于等于nums[j]的情况,表示让nums[j]作为第一个数字,剩下的数字有的组合方法有dp[i-nums[j]]个,最终返回dp[target]的值即可~

 

LeetCode 740. Delete and Earn

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] – 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:
Input: nums = [3, 4, 2]
Output: 6
Explanation:
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.
Example 2:
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation:
Delete 3 to earn 3 points, deleting both 2 and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.
Note:

The length of nums is at most 20000.
Each element nums[i] is an integer in the range [1, 10000].

题目大意:给一个数组,你可以拿起nums[i]并且删除nums[i]并得到nums[i]分数,但是你必须删除数组中所有的nums[i]-1和nums[i]+1,就是说nums[i]-1和nums[i]+1的分数是不可能得到了~求问你能够获得最大的分数会是多少~

分析:数组不是有序的,且在1~10000之间,所以先遍历数组,将i数字所拥有的个数保存在cnt[i]中。设立dp数组,含有10001个元素,(dp[i]表示遍历到i这个数的时候当前情况下的最大值。最后返回dp[10000]的值就是所求),dp[0] = 0, dp[1] = cnt[1]。i从2遍历到10000。对于dp[i],因为如果要了i这个数就不能要i-1和i+1,所以当前i有两个选择:一,要i这个数带来的分数cnt[i] * i,那就不能要dp[i-1]只能要dp[i-2]。二,不要i带来的分数要dp[i-1]的分数。这两个选择取最大值,所以dp[i] = max(dp[i-1], cnt[i] * i + dp[i-2]),最后返回dp[10000]~

 

LeetCode 650. 2 Keys Keyboard

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

Example 1:
Input: 3
Output: 3
Explanation:
Intitally, we have one character ‘A’.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get ‘AA’.
In step 3, we use Paste operation to get ‘AAA’.
Note:
The n will be in the range [1, 1000].

题目大意:一开始给一个A,每次只能复制所有、或者粘贴上一次复制的内容。问要想最后变成n个A,至少得经过多少步~

分析:可以用贪心算法解决,i从2到√n,尝试是否能被n整除,如果能被整除,说明可以通过复制1次粘贴i-1次得到,则计数器ans加上i次,然后将n除以i。再次判断是否能被i整除,直至不能整除为止。然后尝试下一个i……最终n如果等于1则直接返回ans,否则要加上n表示对A复制一次粘贴n-1次~