// @Title: 组合总和 Ⅳ (Combination Sum IV)
// @Author: qisiii
// @Date: 2024-10-31 22:41:32
// @Runtime: 1 ms
// @Memory: 39.9 MB
// @comment: 爬楼梯思想
// @flag: GREEN
class Solution {
    //爬楼梯的思想
    //https://leetcode.cn/problems/combination-sum-iv/solutions/1/zhe-dao-ti-bu-jiu-shi-pa-lou-ti-yao-by-j-h5nn/
    public int combinationSum4(int[] nums, int target) {
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(int n:nums){
                if(i>=n){
                    //dp[10]=dp[4]+dp[6]或者dp[6]+dp[4]
                    dp[i]=dp[i]+dp[i-n];
                }
            }
        }
        return dp[target];
    }
}