蓝湖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.马走日问题

全部评论

相关推荐

06-02 15:17
门头沟学院 Java
心爱的idea:怎么会呢 应该是打招呼有问题 问就说实习6个月全国可飞随时到岗
点赞 评论 收藏
分享
测试糕手手:社会第一课,随便吹牛逼,直接说四个月,别老实。老实人只会被欺负
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务