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

1386. Cinema Seat Allocation

Image
1386.   Cinema Seat Allocation A cinema has  n  rows of seats, numbered from 1 to  n  and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above. Given the array  reservedSeats  containing the numbers of seats already reserved, for example,  reservedSeats[i]=[3,8]  means the seat located in row  3  and labelled with  8  is already reserved.  Return the maximum number of four-person families you can allocate on the cinema seats.  A four-person family occupies fours seats  in one row , that are  next to each other . Seats across an aisle (such as [3,3] and [3,4]) are not considered to be next to each other, however, It is permissible for the four-person family to be separated by an aisle, but in that case,  exactly two people  have to sit on each side of the aisle. Example 1: Input: n = 3, reservedSeats = [[1,2],[1,3]...
Read more

1395. The Barycentre Of The Trees

Description 中文 English For a multi-branch tree, if there is a node  R  with  R  as the root, and the largest sub-tree of all its sub-trees has the least number of nodes, the node  R  is said to be the center of gravity of the tree. Now give you a multi-branch tree with  n  nodes. Find the center of gravity of this tree. If there are multiple centers of gravity, return the one with the lowest number. x[i], y[i] represents the two points of the i-th edge. 2 <= n <= 10^5 1 <= x[i], y[i] <= n Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Given x = `[1]`, y = `[2]`, return `1`. Input: [1] [2] Output: 1 Explanation: Both 1 and 2 can be center of gravity, but the number of 1 is the smallest. Example 2: Given x = `[1,2,2]`, y = `[2,3,4]`, return `2`. Input: [1,2,2] [2,3,4] Output: 2 Explanation: 2 is the center of gravity. Co...
Read more

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