代码随想录打卡 第三十六天

518 零钱兑换 II

class Solution { public: int change(int amount, vector<int>& coins) { vector<unsigned int> dp(amount+1,0); dp[0] = 1; for(int i = 0; i < coins.size();i++){ for(int j = coins[i];j <= amount;j++){ dp[j] += dp[j-coins[i]]; } } return dp[amount]; } };

377 组合总和 IV

class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<unsigned int> dp(target+1,0); dp[0] = 1; for(int j = 0;j <= target;j++){ for(int i = 0;i < nums.size();i++){ if(j >= nums[i] ) dp[j] += dp[j-nums[i]]; } } return dp[target]; } };

卡码网 57 爬楼梯

#include<iostream> #include <vector> using namespace std; int main(){ int m; int n; cin >> n >> m; vector<int> dp(n+1,0); dp[0] = 1; for(int i = 0;i <= n;i++){ for(int j = 1;j <= m;j++){ if(i >= j) dp[i] += dp[i - j]; } } cout << dp[n] << endl; }