564. Combination Sum IV (backpack VI) 元素重复使用 并且 不同order也作为一种情况

int backPackVI(vector<int> &nums, int target) { // write your code here const int size = nums.size(); vector<int> dp(target + 1, 0); dp[0] = 1; //for(int j = target; j >= nums[i]; j--){ for(int j = 1; j <= target; j++){ for(int i = 0; i < size; i++){ if(j >= nums[i]){ dp[j] += dp[j - nums[i]]; } } } return dp[target]; }

 元素重复使用多次

Comments

Post a Comment

Popular posts from this blog

Amazon OA 763. Partition Labels

class Solution { public:     vector<int> partitionLabels(string S) {         // 这是个好题         unordered_map<char, int> mp;         vector<int> res;         const int size = S.size();         if(size == 0){             return res;         }         for(int i = 0; i < size; i++){             mp[S[i]] = i;         }         int start = 0, end = 0;         for(int i = 0; i < size; i++){             end = max(end, mp[S[i]]);             if(i == end){                 res.push_back(i - start + 1);                 start = end + 1;     ...
Read more

1427. Split Array into Fibonacci Sequence

Description 中文 English Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579]. Formally, a Fibonacci-like sequence is a list F of non-negative integers such that: 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type); F.length >= 3; and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2. Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself. Return any Fibonacci-like sequence split from S, or return [] if it cannot be done. 1 <= S.length <= 200 S contains only digits. Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: "123456579" Output: [123,456,579] Example 2: Input: "11235813" Output: [1,1,2,3,5,8,13] Example 3: Input: "112358130" Output: [] Ex...
Read more

05/25 周一

上午8点40多起床，今天天气很热33度最高 上午看了关于H1B的可能ban的事情 然后报税 搞了好久 到现在，吃过饭了。 2020年5月25日13:38:35 听九章上一个转行进入谷歌的讲座， 1，刷题态度 2，抽象总结 3，刷题就是一种学科 不想生活的这么卑微。 别人能做到的，我也可以！ 2020年5月25日17:11:38
Read more