动态规划

剑指 Offer 10- I. 斐波那契数列

经典题目，简单动态规划。

class Solution {
private:
const static long long mod = 1000000007;
public:
    int fib(int n) {
        if(n < 2) {
            return n;
        }
        int a , b, c;
        a = 0, b = 1;
        for(int i = 2 ; i <= n ; i++){
            c = (a + b) % mod;
            a = b, b = c;
        }
        return c;
    }
};

剑指 Offer 10- II. 青蛙跳台阶问题

每一台阶都有两种情况，可能是从前一级跳上来的，也可能是从前两级跳上来的。

class Solution {
private:
const static long long mod = 1000000007;
public:
    int numWays(int n) {
        if(n < 2){
            return 1;
        }
        vector<int> dp(n + 1);
        dp[1] = 1,dp[0] = 1;
        for(int i = 2; i <= n ;i++){
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
        }
        return dp[n]%mod;
    }

降维

注意此题，只和dp[i], dp[i-1],dp[i-2]有关，直接用abc来代替。

class Solution {
private:
const static long long mod = 1000000007;
public:
    int numWays(int n) {
        if(n < 2){
            return 1;
        }
        int a = 1, b = 1, c;
        for(int i = 2; i <= n ;i++){
            c = (b + a) % mod;
            a = b, b = c;
        }
        return c%mod;
    }
};

剑指 Offer 63. 股票的最大利润

不限制交易次数写法(千万注意题目条件！！！)

一开始看错题了，没有看到只能交易一次的限制。但是也因此拓展了思维。设定股票有两种状态，手上有股票和手上没有股票。以此来进行动态规划。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size() + 1, vector<int> (2));
        dp[1][0] = 0, dp[1][1] = -prices[0];
        for(int i = 2; i <= prices.size(); i++){
            dp[i][0] = max(prices[i-1] + dp[i-1][1], dp[i-1][0]);
            dp[i][1] = max(dp[i-1][0] - prices[i -1], dp[i-1][1]);
        }
        return dp[prices.size()][0] > 0? dp[prices.size()][0] : 0;
    }
};//这种写法是计算不限买卖次数时最大利润。

正常写法

dp[i]指的是在i次卖出时的最大利润。在i次卖出有两种可能，一种是根据在i-1次卖出时的最大利益，直接计算在i次卖出的最大利益dp[i] = a=dp[i-1] + price[i-1] - price[i]，第二种情况为直接计算上一次买入，这一次卖出的利益。dp[i] = price[i] - price[i-1]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<int> dp(prices.size() + 1);
        int maxs = 0;
        for(int i = 2; i <= prices.size(); i++){
            dp[i] = max(dp[i-1] + prices[i-1] - prices[i-2], prices[i-1] - prices[i-2]);
            if(dp[i] > maxs){
                maxs = dp[i];
            }
        }
        return maxs;
    }
};

降维

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int a = 0;
        int maxs = 0;
        for(int i = 2; i <= prices.size(); i++){
            a = max(a + prices[i-1] - prices[i-2], prices[i-1] - prices[i-2]);
            if(a > maxs)  maxs = a;
        }
        return maxs;
    }
};

剑指 Offer 42. 连续子数组的最大和（第二次居然没有第一时间想到）

简单动态规划

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};

剑指 Offer 47. 礼物的最大价值

简单二维动态规划

第一次的写法

后面才发现可以不需要判断边界的情况，因为已经初始化的时候边界之外的都为零，并不影像max之后的值。

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n+1,vector<int> (m+1));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j<=m; j++){
                int val = grid[i-1][j-1];
                if(i == 1){
                    dp[i][j] = dp[i][j-1] + val;
                } else if( j == 1){
                    dp[i][j] = dp[i -1][j] + val;
                } else {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + val;
                }
            }
        }
        return dp[n][m];
    }
};

简化

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <=n; j++){
                int price = grid[i-1][j-1];
                dp[i][j] = max(dp[i-1][j] + price, dp[i][j-1] + price);
            }
        }
        return dp[m][n];
    }
};

剑指 Offer 46. 把数字翻译成字符串

青蛙跳台阶的升级版本。但是想到这里仍然不难
这里二次写，千万注意substr的第二个参数为子字符串的长度。

class Solution {
public:
    int translateNum(int num) {
        string src = to_string(num);
        int p = 0, q = 0, r = 1;
        for (int i = 0; i < src.size(); ++i) {
            p = q; 
            q = r; 
            r = 0;
            r += q;
            if (i == 0) {
                continue;
            }
            auto pre = src.substr(i - 1, 2);
            if (pre <= "25" && pre >= "10") {
                r += p;
            }
        }
        return r;
    }
};

剑指 Offer 48. 最长不含重复字符的子字符串

笨比写法（动态规划+string）

这一题我真的写了半天，用了最蠢的方式来写的。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        string str = "";
        int n = s.size(), maxs = 0;
        vector<int> dp(n + 1);
        for(int i = 1; i <= n; i++){
            int p = str.find(s[i-1], 0);//查找字符第一次出现的位置
            str+= s[i-1];
            if(p == -1){
                dp[i] = dp[i-1] + 1;
            } else {
                dp[i] = str.size() - p - 1;
                str = str.substr(p+1);//更新str
            }
            maxs = max(dp[i], maxs);
        }
        return maxs;
    }
};

优化空间

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        string str = "";
        int n = s.size(), maxs = 0;
        int a = 0, b = 0;
        for(int i = 1; i <= n; i++){
            int p = str.find(s[i-1], 0);
            str+= s[i-1];
            if(p == -1){
                b = a + 1;
                a = b;
            } else {
                a = str.size() - p - 1;
                str = str.substr(p+1);
            }
            maxs = max(a, maxs);
        }
        return maxs;
    }
};

哈希表

与上图不同的是，用一个哈希表来储存每个字符最后一次出现的位置。

哈希表+滑窗

感觉滑窗更好写，每次遇到哈希表中有的就记录一次，然后滑动。这里千万注意maxs的初始化！！！！出现了很多莫名其妙的问题，初始化可以解决一切问题。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size(), ret = 0, front = 0, maxs = 0;
        unordered_map<char, int> hash;
        for(int i = 0; i < n; i++){
            hash[s[i]]++;
            ret++;
            if(hash[s[i]] > 1){
                while(s[front] != s[i]){
                    hash[s[front]]--;
                    front++;
                    ret--;
                }
                hash[s[i]]--;
                front++;
                ret--;
            }
            maxs = max(ret , maxs);
        }
        return maxs;
    }
};

剑指 Offer 60. n个骰子的点数（百度面试题，难）

• 找出状态转移表达式
• 确定是从前往后正向递推

很难，这里的想法就非常难，根据骰子少一个来往后推。

class Solution {
public:
    vector<double> dicesProbability(int n) {
        //因为最后的结果只与前一个动态转移数组有关，所以这里只需要设置一个一维的动态转移数组
        //原本dp[i][j]表示的是前i个骰子的点数之和为j的概率，现在只需要最后的状态的数组，所以就只用一个一维数组dp[j]表示n个骰子下每个结果的概率。
        //初始是1个骰子情况下的点数之和情况，就只有6个结果，所以用dp的初始化的size是6个
        vector<double> dp(6, 1.0 / 6.0);
        //只有一个数组
        //从第2个骰子开始，这里n表示n个骰子，先从第二个的情况算起，然后再逐步求3个、4个···n个的情况
        //i表示当总共i个骰子时的结果
        for (int i = 2; i <= n; i++) {
            //每次的点数之和范围会有点变化，点数之和的值最大是i*6，最小是i*1，i之前的结果值是不会出现的；
            //比如i=3个骰子时，最小就是3了，不可能是2和1，所以点数之和的值的个数是6*i-(i-1)，化简：5*i+1
            //当有i个骰子时的点数之和的值数组先假定是tmp
            vector<double> tmp(5 * i + 1, 0);
            //从i-1个骰子的点数之和的值数组入手，计算i个骰子的点数之和数组的值
            //先拿i-1个骰子的点数之和数组的第j个值，它所影响的是i个骰子时的temp[j+k]的值


            //这里是正推的写法
            for (int j = 0; j < dp.size(); j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
};

剑指 Offer II 088. 爬楼梯的最少成本(简单动规)

• 注意边界情况即可，注意这里的终点是dp[n]，也就是下标为n时的最小花费，也就是说要超出这个cost数组才行

  class Solution {
  public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n+1);
        for(int i = 2; i <= n; i++) {
            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[n];
    }
  };
  

  剑指 Offer II 089. 房屋偷盗（经典动规）

  class Solution {
  public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1);
        dp[1] = nums[0];
        for(int i = 2; i <= n; i++){
            dp[i] = max(dp[i-1], dp[i-2]+nums[i-1]);
        }
        return dp[n];
    }
  };
  

  剑指 Offer II 090. 环形房屋偷盗（重点）

  class Solution {
  public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) {
            return nums[0];
        }
        return max(helper(nums, 1, n), helper(nums, 0, n-1));//注意这里的区间是左闭右开
    }
    int helper(vector<int>& nums, int l , int r) {
        int n = nums.size();//注意这里！！！
        vector<int> dp(n+1);
        dp[l+1] = nums[l];
        for(int i = l + 2; i <= r; i++) {
            dp[i] = max(dp[i-2]+nums[i-1], dp[i-1]);
        }
        return dp[r];
    }
  };
  

  剑指 Offer II 091. 粉刷房子

  遇到麻烦的问题可以分解一下

  class Solution {
  public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<vector<int>> dp(n+1, vector<int>(3));
        for(int i = 1; i <= n; i++) {
            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0];
            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1];
            dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + costs[i-1][2];
        }
        return min(dp[n][0], min(dp[n][1], dp[n][2]));
    }
  };
  

  剑指 Offer II 092. 翻转字符（要看/特殊）

  dp的第一维表示s的前i个字符已经满足条件，第二维表示以0还是1结尾的。dp[i][j]的意思就是前i个字符以j结尾满足条件需要多少次操作。根据条件可知，0的前面不可能是1之可能为0,因此dp[i][0] = dp[i-1][0]，后面是否+1则取决于当前的字符是否为0,如果为0则不需要变化，不为0则需要一次操作。而1的前面即可能为0也可能为1,取两者之间操作次数较小的一个。因此dp[i][1] = min(dp[i-1][1], dp[i-1][0])，后面是否+1取决于当前元素是否为1。

  class Solution {
  public:
    int minFlipsMonoIncr(string s) {
        int n = s.size();
        vector<vector<int>> dp(n+1, vector<int>(2));
        for(int i = 1; i <= n; i++) {
            if(s[i-1] == '0') {
                dp[i][0] = dp[i-1][0];
                dp[i][1] = min(dp[i-1][1], dp[i-1][0]) + 1;
            } else {
                dp[i][0] = dp[i-1][0] + 1;
                dp[i][1] = min(dp[i-1][1], dp[i-1][0]);
            }
        }
        return min(dp[n][0], dp[n][1]);
    }
  };
  

  剑指 Offer II 093. 最长斐波那契数列（哈系表+dp+重点）

• 使用一个二维数组来做dp，表示以arr[i]结尾arr[j]为倒数第二个的斐波那契数列最大长度。

• 用哈系表存下标，方便查找符合条件的情况。

  class Solution {
  public:
    int lenLongestFibSubseq(vector<int>& arr) {
        vector<vector<int>> dp(arr.size(), vector<int>(arr.size()));
        unordered_map<int, int> mp;
        for (int i = 0; i < arr.size(); ++i) {
            mp[arr[i]] = i;
        }
  
        int ret = 0;
        for (int i = 1; i < arr.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                int temp = arr[i] - arr[j];
                // 存在 k 使得 A[i] = A[j] + A[k] (0 <= k < j < i)
                if (mp.count(temp) && mp[temp] < j) {
                    dp[i][j] = dp[j][mp[temp]] + 1;
                }
                // 不存在 k 使得 A[i] = A[j] + A[k] (0 <= k < j < i)
                else {
                    dp[i][j] = 2;//这里是方便后面的dp
                }
                ret = max(ret, dp[i][j]);
            }
        }
  
        return ret > 2 ? ret : 0;
    }
  };
  

  剑指 Offer II 095. 最长公共子序列（基本）

  class Solution {
  public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        for(int i = 1; i <= n; i++) {
            for(int j= 1; j <= m; j++) {
                if(text1[i-1] == text2[j-1]) {
                    dp[i][j] = dp[i-1][j-1]+1;
                } else {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[n][m];
    }
  };
  

  剑指 Offer II 096. 字符串交织（特殊，写不出来）

• 这里的dp[i][j]的意思是s1的前i个字符和s2的前j个字符是否能完成字符串交织。

• dp可以枚举所有情况，所以包含了不同顺序的情况

  class Solution {
  public:
    bool isInterleave(string s1, string s2, string s3) {
        auto f = vector < vector <int> > (s1.size() + 1, vector <int> (s2.size() + 1, false));
  
        int n = s1.size(), m = s2.size(), t = s3.size();
  
        if (n + m != t) {
            return false;
        }
  
        f[0][0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[i][j] |= (f[i - 1][j] && s1[i - 1] == s3[p]);
                }
                if (j > 0) {
                    f[i][j] |= (f[i][j - 1] && s2[j - 1] == s3[p]);
                }
            }
        }
        return f[n][m];
    }
  };
  

  剑指 Offer II 094. 最少回文分割（困难）

• 首先通过动态规划标记所有位置是否为回文串

• 然后动规i之前的分割回文串的数量，使用for循环来遍历j～i是否是回文串。

  class Solution {
  public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<int>> g(n, vector<int>(n, true));
  
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];//先把所有回文串打上标记
            }
        }
        vector<int> f(n, INT_MAX);
        for (int i = 0; i < n; ++i) {
            if (g[0][i]) {
                f[i] = 0;
            } else {
                for (int j = 0; j < i; ++j) {
                    if (g[j + 1][i]) {
                        f[i] = min(f[i], f[j] + 1);//分割的情况
                    }
                }
            }
        }
  
        return f[n - 1];
    }
  };//动态规划
  

  剑指 Offer II 097. 子序列的数目（hard）

  class Solution {
  public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        //表示t的前j个元素，在s的前i个元素中作为子序列出现的个数
        vector<vector<unsigned>> dp(m + 1, vector<unsigned> (n + 1, 0));
        for(int i = 0; i <= m; i++) {
            dp[i][0] = 1;//空字符串是任何字符串的子串
        }
        for (int i = 1; i < m + 1; ++i) {
            for (int j = n; j > 0; --j) {
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i-1][j - 1] + dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[m][n];
    }
  };
  

  剑指 Offer II 098. 路径的数目

  基础题目，边界问题需要注意。
  这里的上边和左边都是只有一种路径。

  class Solution {
  public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
  };
  

  剑指 Offer II 099. 最小路径之和

  基础问题，注意边界问题。
  和上题类似

  class Solution {
  public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(m, INT_MAX));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if( i == 0&&j==0) {
                    dp[i][j] = grid[i][j];
                } else if(i == 0) {
                    dp[i][j] = dp[i][j-1] + grid[i][j];
                } else if(j == 0) {
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                } else {
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j];
                }
            }
        }
        return dp[n-1][m-1];
    }
  };
  

  剑指 Offer II 100. 三角形中最小路径之和

  基础问题，注意边界问题。这里是优化以后的答案。

  class Solution {
  public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size(), m = triangle[n-1].size();
        vector<int> dp(m+1);
        for(int i = 1; i <= n; i++) {
            for(int j = triangle[i-1].size(); j >= 1; j--) {
                if(j == 1) {
                    dp[j] = dp[j] + triangle[i-1][j-1];
                } else if(j == triangle[i-1].size()) {
                    dp[j] = dp[j-1] + triangle[i-1][j-1];
                } else dp[j] = min(dp[j-1], dp[j]) + triangle[i-1][j-1];
            }
        }
        return *min_element(dp.begin()+1, dp.end());
    }
  };
  

  背包问题

  剑指 Offer II 101. 分割等和子集（01背包问题）

  对于每个元素只有选取和不选取，没有重复选取的情况。

  class Solution {
  public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0), n = nums.size();
        int target = sum/2;
        if(sum%2 != 0) return false;
        vector<vector<int>> dp(n+1, vector<int>(target+1));
        for(int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        for(int i = 1; i <= n; i++) {
            int num = nums[i-1];
            for(int j = 0; j <= target; j++) {
                if(j >= num) {
                    dp[i][j] = dp[i-1][j-num]|dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[nums.size()][target];
    }
  };
  

  空间压缩

  class Solution {
  public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0), n = nums.size();
        int target = sum/2;
        if(sum%2 != 0) return false;
        vector<bool> dp(target+1);
        dp[0] = true;
        for(int i = 1; i <= n; i++){
            for(int j = target; j >= nums[i-1]; j--){
                    dp[j] = dp[j]||dp[j-nums[i-1]];
            }
        }
        return dp[target];
    }
  };
  

  剑指 Offer II 102. 加减的目标值（太细节了）

  题目中明确数组内所有的数字都为正数，如果把所有取正号的数字之和记为 p，剩下的取负号的数字之和记为 q，若存在符合题意的组合则 p - q = target，同时记所有的数字之和为 p + q = sum。将以上两式相加得 p = (target + sum) / 2。因此，这个问题就等价于计算从数组中选出和为 (target + sum) / 2 的数字的方法的数目。这和前面的面试题 101 非常相似，是一个典型的 0-1 背包问题，可以使用动态规划。

  class Solution {
  public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int& num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = nums.size(), neg = diff / 2;
        vector<vector<int>> dp(n + 1, vector<int>(neg + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }
  };
  

  笨蛋解法

• 记得要列举出所有的情况，这里包括负数！！！

  class Solution {
  public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size(), sum = accumulate(nums.begin(), nums.end(), 0);
        if(target>sum||target<-sum) return 0;
        vector<vector<int>> dp(n+1, vector<int>(2*sum+1));
        dp[0][sum] = 1;
        for(int i = 1; i <= n; i++) {
            int num = nums[i-1];
            for(int j = -sum; j <= sum; j++) {
                int k = j+sum;
                if(k >= num && k <= 2*sum-num) {
                    dp[i][k] = dp[i-1][k-num]+dp[i-1][k+num];
                } else if(k >= num) {
                    dp[i][k] = dp[i-1][k-num];
                } else if(k <= 2*sum-num) {
                    dp[i][k] = dp[i-1][k+num];
                } else {
                    dp[i][k] = 0;
                }
            }
        }
        return dp[n][target+sum];
    }
  };
  

  剑指 Offer II 103. 最少的硬币数目（完全背包问题）

• 注意和01背包问题的差别是后面是dp[i][j-num]，就是把i-1换成了1,主要是公式推理的结果。

  class Solution {
  public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<int>> dp(n+1, vector<int>(amount+1, INT_MAX-1));
        for(int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for(int i = 1; i <= n; i++) {
            int num = coins[i-1];
            for(int j = 0; j <= amount; j++) {
                if(j >= num)  dp[i][j] = min(dp[i-1][j], dp[i][j-num]+1);
                else dp[i][j] = dp[i-1][j];
            }
        }
        return dp[n][amount] == (INT_MAX-1)? -1:dp[n][amount];
    }
  };
  

  剑指 Offer II 104. 排列的数目（太难了！！！）

  dp[i]表示选取的元素之和等于i的方案数。dp[i] = dp[i-num1]+dp[i-num2]…..。这里注意越界的问题。

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