8.27京东笔试

#include<iostream> #include<vector> using namespace std; int solution(vector<int>& choice, int r, vector<int>& dp) { if (r < 0) return 0; if (dp[r] != 0 || r == 0) return dp[r]; long cur = 0; for (auto i : choice) { cur += solution(choice, r - i, dp); } if (cur >= 1e9 + 7)  cur =cur % (long)(1e9 + 7); dp[r] = cur; return cur; } int main() { int n, m; cin >> n >> m; int t; vector<int> data; while (n-- && cin >> t) data.push_back(t); vector<int> dp(m+1, 0); dp[0] = 1; cout << solution(data, m, dp); }

看起来用零钱兑换2的思路，两个for换一下位置就行了吧（我没考这题） class Solution:     def change(self, amount: int, coins: List[int]) -> int:         dp = [0] * (amount + 1)         dp[0] = 1         for x in range(amount + 1):  # 和原题相比两个for换了位置             for i in coins:                 if x >= i:                     dp[x] += dp[x - i]         return dp[-1] coin就是牌，amount是血量 输入3 [1,2,2] 输出5（代码里要加个mod）

有，刚开始用零钱兑换的思路，只过了27，发现牌序不一样算不同结果，没想明白dp🤣，后来换了dfs&nbsp;55超时，菜哭了

这个dp就好了，我想问下第一题我一直是通过90%是怎么回事😂