关键词网站推广,网站建站网站45133,wordpress神马优化,女生就业前景最好的十大热门专业377. 组合总和 Ⅳ
题目#xff1a;
给一个正整数数组和一个正整数目标值#xff0c;数组的每个元素可取无限次#xff0c;求总额达到目标值的最大排列数。 dp[j]含义#xff1a;
dp[j]#xff1a;达到目标值j的整数组合数为dp[j]
递推公式#xff1a;
求装满背包有几…377. 组合总和 Ⅳ
题目
给一个正整数数组和一个正整数目标值数组的每个元素可取无限次求总额达到目标值的最大排列数。 dp[j]含义
dp[j]达到目标值j的整数组合数为dp[j]
递推公式
求装满背包有几种方法组合排列数用dp[j] dp[j - nums[i]];
初始化:
dp[0]1
遍历顺序
先物品后背包最大组合数
先背包后物品最大排列数
总代码
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target 1, 0);dp[0] 1;for (int i 0; i target; i) { // 遍历背包for (int j 0; j nums.size(); j) { // 遍历物品
//C测试用例有两个数相加超过力扣int的数据所以需要在if里加上dp[i] INT_MAX - dp[i - num]。if (i - nums[j] 0 dp[i] INT_MAX - dp[i - nums[j]]) {dp[i] dp[i - nums[j]];}}}return dp[target];}
}; 70.魔改爬楼梯
题目代码随想录
一步一个台阶两个台阶三个台阶.......直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢
思路
相当于给了一个1-m的数组数组元素可取无数次到达总数为m的最大排列数。
dp[j]含义
dp[i]爬到有i个台阶的楼顶有dp[i]种方法。
递推公式
求装满背包爬到目标楼梯有几种方法组合排列数用dp[j] dp[j - nums[i]];
nums[i]一般指当前为 i 的物品这题num[i]有1----m但没有数组的形式所以dp[j]dp[j-i]
初始化:
dp[0]1
遍历顺序
先物品后背包最大组合数
先背包后物品最大排列数
求排列数所以先背包后物体
总代码
class Solution {
public:int climbStairs(int n) {vectorint dp(n 1, 0);dp[0] 1;for (int i 1; i n; i) { // 遍历背包for (int j 1; j m; j) { // 遍历物品if (i - j 0) dp[i] dp[i - j];}}return dp[n];}
};
