标签： LeetCode OJ

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～

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]的值即可～

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]～

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次～

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
Note:
cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].

题目大意：爬n阶的楼梯，每层都有一个cost值（0～n-1），每次可以爬1层或者2层，求爬完全程的最小花费cost（可以从第0层开始也可以从第1层开始）

分析：dp数组，每次dp[i] = cost[i] + min(dp[i-1], dp[i-2])，最终返回dp[n-1]和dp[n-2]中较小的那个～

Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.

However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.

Example:
Input: [1000,100,10,2]
Output: “1000/(100/10/2)”
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in “1000/((100/10)/2)” are redundant,
since they don’t influence the operation priority. So you should return “1000/(100/10/2)”.

Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2
Note:

The length of the input array is [1, 10].
Elements in the given array will be in range [2, 1000].
There is only one optimal division for each test case.

题目大意：给定一个正整数列表，相邻的整数将执行浮点除法。 例如[2,3,4] – > 2/3/4。但是，您可以在任何位置添加任意数量的括号以更改操作的优先级。您应该找到如何添加括号以获得最大结果，并以字符串格式返回相应的表达式，你的表达不应该包含多余的括号。

分析：要想得到最大的结果，只要使除数尽可能大，被除数尽可能小。被除过的数一定会变得更小，所以括号加在第一个数后面，括号内的数按从前到后顺序（不用添加冗余的括号）即可～