leetcode 377. 组合总和 Ⅳ（dp）

377. 组合总和 Ⅳ - 力扣（LeetCode）

dp，跟完全背包反着来，可以当作是爬楼梯来做，相当于每次爬的楼梯数是从数组种选的。

 1 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
 2 #define bug(x) cout<<#x<<" is "<<x<<endl;
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 typedef long long ll;
 6 class Solution {
 7 public:
 8     int combinationSum4(vector<int>& nums, int target) {
 9         vector<int>d(1005,0);
10         d[0]=1;
11         for(int i=0;i<=target;i++){
12             for(int j=0;j<nums.size();j++){
13                 if(i-nums[j]>=0&&d[i]<INT_MAX-d[i-nums[j]])d[i]+=d[i-nums[j]];
14             }
15         }
16         return d[target];
17     }
18 };
19 int main(){
20     vector<int>v={10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990,111};
21     Solution A;
22     cout<<A.combinationSum4(v,999);
23 }