蓝湖7.10

1.一个数组，求数组中部分元素满足targer的组合的个数。典型的0-1背包问题

public int pack(int[] nums,int target){
        int n = nums.length;
        int[][] dp = new int[n+1][target+1];
        dp[0][0] =1;
        for(int i = 1;i<=n;i++){
            for(int j = 0;j<=target;j++){
                if(j - nums[i-1] <0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                }

            }
        }
        return dp[n][target];
    }

可以进行优化，映射到一维：

public int pack(int[] nums,int target){
        int n = nums.length;
        int[] dp = new int[target+1];
        dp[0] =1;
        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];
    }

2.一个球的回溯问题：大致为有n个白球和m个黑球，将他们从左到右排成一排，满足一个条件：对于每一个i满足1<=i<=m+n,记录从第一个球到第i个球中的白球数量为w,黑球数量为b,满足w<=b+k,求一个有多少种满足条件的排列？
最后结果取余10^9+7

3.马走日问题