[剑指 Offer II 104. 排列的数目] class Solution {

public int combinationSum4(int[] nums, int target) {
    int [] dp = new int [target + 1];
    dp[0] = 1;
    for (int t = 1; t < target + 1; t ++){
        for (int y : nums){
            int x = t - y;
            if (0 <= x){
                if ((long)dp[t] + dp[x] <= Integer.MAX_VALUE)
                    dp[t] += dp[x];
            }
        }
    }
    return dp[target];
}

}

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

public int minimumTotal(List<List<Integer>> triangleList) {
    int[][] arr = new int[triangleList.size()][200];
    int len = arr.length;

    for(int i=0;i<arr.length;i++){
        for(int j=0;j<=i;j++){
            arr[i][j] = triangleList.get(i).get(j);
        }
    }

    for(int i=1;i<len;i++){
        arr[i][0] += arr[i-1][0];
        arr[i][i] += arr[i-1][i-1];
        for(int j=1;j<i;j++){
            arr[i][j] += Math.min(arr[i-1][j-1],arr[i-1][j]);
        }
    }

    int min = arr[len-1][0];
    for(int i=0;i<len;i++){
        System.out.println(arr[len-1][i]);
        if(arr[len-1][i] < min){
            // min = arr[len-1][i];
            min = Math.min(min, arr[len - 1][i]); 
        }
    }
    return min;
}

}

整数分解为若干项之和

include using namespace std;

int a[31], n, sum = 0, count = 1, top = 0; void Dfs(int i) { if (sum == n) { cout << n << "="; for (int j = 0; j < top - 1; j++) { cout << a[j] << "+"; } cout << a[top - 1]; if (count % 4 == 0 || a[top - 1] == n) cout << endl; else cout << ";"; count++; } else if (sum < n) { for (int j = i; j <= n; j++) { a[top++] = j; sum += j; Dfs(j); sum -= j; top--; } } } int main() { cin >> n; Dfs(1); return 0; }

假设有N项物品，大小分别为 int n, m = 0; cin >> n; int s[n][2], b[n]; for (int i = 0; i < n; i++){

//第一维代表第i个物品重量，第二维表示装在第j个箱子
cin >> s[i][0];  
b[i] = 100;

} for (int i = 0; i < n; i++){

int flag = 1, j = 0; //j代表要放在第几个箱子里
while (flag){
    if (b[j] >= s[i][0]){
        // flag=0，代表物品已经放在箱子里了，退出循环
        flag = 0; 
        b[j] -= s[i][0];
        s[i][1] = j + 1;;
    }
    else{
        j++;
        if (j > m) m = j; //更新所需要的箱子数量
    }
}

} for (int i = 0; i < n; i++){

cout << s[i][0] << " " << s[i][1] << endl;

} cout << m + 1 << endl; return 0;

三数之和 class Solution {

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> list = new ArrayList();
    int len = nums.length;
    if(nums == null || len < 3) return ans;
    Arrays.sort(nums); // 排序
    for (int i = 0; i < len ; i++) {
        if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环，因为已经排序好了的
        int L = i+1;
        int R = len-1;
        while(L < R){
            int sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
             list.add(Arrays.asList(nums[i],nums[L],nums[R]));
                L++;
                R--;
            }
            else if (sum < 0) L++;
            else if (sum > 0) R--;
        }
    }
    //去重
    HashSet set = new HashSet(list);   
    list.clear();   
    list.addAll(set);  
    return list;
}

}

用最少数量的箭引爆气球 int end = points[0][1];

    int num = 1;
    for(int[] point : points){
        if(point[0] > end){
            //一旦头还没到上一个的尾巴，更新尾巴，用新的箭
            end = point[1];
            num++;
        }
    }