精华内容
下载资源
问答
  • Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]. ...//dp[i]表示原数组是否可以取出若干个数字,其为i class Solution { public: ...

            Input: [1, 5, 11, 5]
            Output: true
            Explanation: The array can be partitioned as [1, 5, 5] and [11].

    #include<iostream>
    #include<vector>
    using namespace std;
    
    
    
    //dp[i]表示原数组是否可以取出若干个数字,其和为i 
    class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int sum = 0;
            for(int i = 0 ; i < nums.size() ; i ++)
            {
            	sum += nums[i];
    		}
    
    		cout << "sum=" << sum << endl;
    		
    		if(sum % 2 != 0)  //判断整个和是否为偶数
    			return 0;
    
    		int target = sum / 2;
    		cout << "target=" << sum/2 << endl;
    		
    		vector<int> dp(target + 1, 0);
    		dp[i]表示原数组是否可以取出若干个数字,其和为i 
    		dp[0] = 1;  //边界
    		
    		for(int i = 0 ; i < nums.size(); i ++)
    		{
    		    cout << "nums[i]=" << nums[i] << endl;
    			for(int j = target; j >= nums[i]; j --)
    			{   
    			    //如果 dp[j - nums[i]] 为true的话,说明现在已经可以组成 j-nums[i] 这个数字了
    			    //再加上nums[i],就可以组成数字j了
    			    cout << "j=" << j << "," << "dp[j]=" << dp[j] << "," <<  dp[j-nums[i]] << endl;
    				dp[j] = dp[j] || dp[j-nums[i]];
    			}
    
    			cout << "--------------------------------------------" <<endl;
    		}
    		return dp[target];
        }
    };
     
    int main()
    {
    	vector<int> temp {1, 3, 2, 4};
    
    	Solution text;
    	cout << text.canPartition(temp) << endl;
    	return 0;
    }

    打印:

    sum=10
    target=5
    nums[i]=1
    j=5,dp[j]=0,0
    j=4,dp[j]=0,0
    j=3,dp[j]=0,0
    j=2,dp[j]=0,0
    j=1,dp[j]=0,1              //dp[1] = 1 ,数组是否可以取出若干个数字,其和为1,因为第一个数为1
    --------------------------------------------
    nums[i]=3
    j=5,dp[j]=0,0
    j=4,dp[j]=0,1            //dp[4] = 1 ,数组是否可以取出若干个数字,其和为4,因为dp[1]=1,nums[i]=3,相加和刚好是4
    j=3,dp[j]=0,1            //dp[3] = 1 ,数组是否可以取出若干个数字,其和为3,刚好这个数为3
    --------------------------------------------
    nums[i]=2
    j=5,dp[j]=0,1            //dp[5] = 1 ,数组是否可以取出若干个数字,其和为5,因为d[3]=1
    j=4,dp[j]=1,0            //dp[4] = 1 ,上面已经为1了
    j=3,dp[j]=1,1            //dp[3]和dp[1]都为1
    j=2,dp[j]=0,1            //dp[0]为1
    --------------------------------------------
    nums[i]=4
    j=5,dp[j]=1,1           //d[5]和dp[1]都为1
    j=4,dp[j]=1,1           //d[4]和dp[0]都为1
    --------------------------------------------
    1

    上面的思路相对数组中每个数求dp,最后就会找到dp[target]是否为true,如果 dp[j - nums[i]] 为true的话,说明现在已经可以组成 j-nums[i] 这个数字了,再加上nums[i],就可以组成数字j了。当j=target是同样道理,要想找到dp[target]为true,就找找到数组中几个值的和为target时,对应下标的dp值为true,这样反推dp[target]为true。

     

    参考地址:https://blog.csdn.net/qq_40320556/article/details/89875463

    展开全文
  • 给一只含有正整数的非空数组, 判断这个数组是否可以划分为 两个元素和相等的子集。 注意事项: 所有数组元素不超过100. 数组大小不超过200. 样例: 给一数组 [1, 5, 11, 5] , 返回 true , 两个子集:[1, 5, 5], ...

    给一只含有正整数的非空数组, 判断这个数组是否可以划分为 两个元素和相等的子集。

    注意事项: 
    所有数组元素不超过100. 
    数组大小不超过200.

    样例: 
    给一数组 [1, 5, 11, 5] , 返回 true ,  
    两个子集:[1, 5, 5], [11] 
    给一数组 [1, 2, 3, 9] , 返回 false

    思路: 
    动态规划,对于数组nums,判断奇偶性,若为奇数,肯定不可能分成两个相等的数, 
    若为偶数,令sum为数组nums元素和的一半。构建数组dp[len][sum],dp[i][j]表示nums的第一个元素到 
    第i个元素构成的集合中,是否存在使得和为j的子集。 
    状态转换方程为:

    #ifndef C588_H
    #define C588_H
    #include<iostream>
    #include<vector>
    using namespace std;


    class Solution {
    public:
        /*
        * @param nums: a non-empty array only positive integers
        * @return: true if can partition or false
        */
        bool canPartition(vector<int> &nums) {//nums为存放数据的vector矢量数组
            // write your code here
            int sum = 0;
            for (auto c : nums)//相当于java的for each。v是一个可遍历的容器或流,变量c用来遍历nums容器(int类型的vector)的每一个元素。


                sum += c;  //
            if (sum % 2 != 0)
                return false;
            else
                sum /= 2;

    //sum为数组nums元素和的一半。构建数组dp[len][sum],dp[i][j]表示nums的第一个元素到第i个元素构成的集合中,是否存在使得

    //和为j的子集。 
            int len = nums.size();
            vector<vector<bool>> dp(len + 1, vector<bool>(sum + 1, false));
            for (int i = 0; i <= len; ++i)
                dp[i][0] = true;     //和为0是不可能存在的,因为这是一个正整数vector
            for (int i = 1; i <= len; ++i)          //遍历数组
            {
                for (int j = 1; j <= sum; ++j) 
                {
                    if (j >= nums[i - 1])   //如果j大于等于第i个元素
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];  那么我们就将dp【i】【j】设置为要么满足上一层中和为j的元素,要么//

     

    //就满足和等于j减去元素的第i位。背包问题即,将问题变为一个个的小问题,高层由低层决定。

    也就是把A问题  “前i位的和能不能等于j”  转化为——B问题 “前i-1位的和能不能等于j” 和C 问题 “前i-1位的和能不能等于j- nums【i-1】”,然后以此类推。
                    else
                        dp[i][j] = dp[i - 1][j];
                }
            }
            return dp[len][sum];
        }
    };
    #endif

    展开全文
  • 划分数组为和相等的两部分 416. Partition Equal Subset Sum (Medium) 题目描述:   给定一个数组,判断其是否可以被划分为相等的两部分。 思路分析:   我们可以换一种思路,判断其是否可以分为相等的两部分,...

    划分数组为和相等的两部分

    416. Partition Equal Subset Sum (Medium)

    题目描述:

      给定一个数组,判断其是否可以被划分为相等的两部分。

    思路分析:

      我们可以换一种思路,判断其是否可以分为相等的两部分,其实就是看是否能在数组中挑选出和为数组和一半的序列。那么就可以转化为背包问题,在N个数中挑选数字使其和为数组和的一半,状态转移方程为:

      dp[i]=dp[i] || dp[i-num]

    代码:

    public boolean canPartition(int []nums){
        int sum=0;
        for(int num:nums){
            sum=sum+num;
        }
        if(sum%2!=0)
            return false;
        int target=sum/2;
        boolean []dp=new boolean [target+1];
        dp[0]=true;
        for(int num:nums){ //0-1背包一个物品只能用一次
            for(int i=target;i>=num;i--){ //从后向前,先计算dp[i],再计算dp[i-num]
                dp[i]=dp[i]||dp[i-num];
            }
        }
        return dp[target];
    }

    转载于:https://www.cnblogs.com/yjxyy/p/11119379.html

    展开全文
  • 动态规划和回溯

    千次阅读 2019-09-05 08:04:57
    动态规划: 例子:求两个字符串的最大公共子序列,公式. 分析: 根据分析不相等的话右下角为左上的最大值。相等的时候是左上角+1。 变换的问题:一旦左面是1,则右面全是1。 相当于a与random 同理...

    动态规划:

          例子:求两个字符串的最大公共子序列,公式.

             

       分析:

            根据分析不相等的话右下角为左和上的最大值。相等的时候是左上角+1。

           变换的问题:一旦左面是1,则右面全是1。

            相当于a与random

             同理竖着的也是。

             最后的结果。

             代码:

           

    package lcs;
    
    public class Lcs {
        public int findLCS(String A,String B){
            int n = A.length();
            int m = B.length();
            char[] a = A.toCharArray();
            char[] b = B.toCharArray();
            int [][] dp = new int[n][m];
            //第一行的
            for(int i = 0;i<n;i++){
                if(a[i] == b[0]){
                    dp[i][0] = 1;
                    for(int j = i+1;j<n;j++){
                        dp[j][0] = 1;
                    }
                    break;
                }
            }
            //第一列的
            for(int i = 0;i<m;i++){
                if(a[0] == b[i]){
                    dp[0][i] = 1;
                    for(int j = i+1;j<m;j++){
                        dp[0][j] = 1;
                    }
                    break;
                }
            }
            for(int i = 1;i<n;i++){
                for(int j = 1;j<m;j++){
                    if(a[i] == b[j]){
                        dp[i][j] = dp[i-1][j-1]+1;
                    }else{
                        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                    }
                }
            }
            for(int i = 0;i<n;i++){
                for(int j = 0;j<m;j++){
                    System.out.print(dp[i][j]+" ");
                }
                System.out.println();
            }
            return dp[n-1][m-1];
        }
    
        public static void main(String [] args){
            Lcs lcs = new Lcs();
            int findLCS = lcs.findLCS("android", "random");
            System.out.println("公共子串"+findLCS);
        }
    }
    

       回溯算法:

                  题目是皇后在行和列和对角线不会出现碰撞的。

               

               cols[m]m是第几列,值是第m列的第几行是有皇后的。

               代码:

               

    package queen;
    public class Queen {
        public static int num = 0;//累计方案
        public static final int MAXQUEEN = 8;//放置的皇后数量放几个棋盘就是多大
        public static int[] cols = new int[MAXQUEEN];//定义cols数组,表示8列棋子皇后摆放的位置  下标是列值是行
        public void getCount(int n){
            boolean [] rows = new boolean[MAXQUEEN];//记录每列每个方格是否可以放皇后
            for(int m = 0;m<n;m++){//m是列
                rows[cols[m]] = true;//cols[m]值是第几行有皇后m是列,前几列的这几行是不能填的
                int d = n - m;//斜对角 列数之间的差距
                //正斜方向就是左面低右面高
                if(cols[m]-d>=0){ rows[cols[m] -d] = true;//这个是算的哪个不能填的,cols[m]3是行-d为差值1=2则第二行是不能填写的。
                    }//反斜方向就是右面低左面高
                if(cols[m]+d<=(MAXQUEEN-1)){
                    rows[cols[m]+d] = true;//同理
                }
            }
            for(int i = 0;i<MAXQUEEN;i++){//MAXQUEEN也是行也是列 //到此知道了哪些位置不能放皇后i行
                if(rows[i]){
                    //不能放
                    continue;
                }
                cols[n] = i;//n是列cols[n]是第几行
                if(n<MAXQUEEN-1){//最后一列放好了就是好了
                    getCount(n+1);
                }else{            //下面可能仍然有合法位置
                    //找到完整的一套方案
                    num++;
                    printQueen();
                }
            }
        }
        private void printQueen() {
            System.out.println("第"+num+"种方案");
            for(int i = 0;i<MAXQUEEN;i++){
                for(int j = 0;j<MAXQUEEN;j++){
                    if(i == cols[j]){ System.out.print("0 ");
                    }else{ System.out.print("+ "); }
                }System.out.println();
            }
        }
        public static void main(String[] args){
            Queen queen = new Queen();queen.getCount(0);
        }
    }
    

     

    展开全文
  • 本题题意很简单,直接设置一个左右数组来求解左边元素右边元素之,然后遍历即可 代码如下: #include #include #include #include #include #include #include #include #...
  • 是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 ...
  • //表示第j个及地j之前的元素的组合的为0的存在性为1 因为第j个及地j之前的元素一个都不选结果就是0 } for (int i = 1; i; i++) //loop从第一个元素到最后一个元素 { for (int j = 1; j; j++) //loop从1到...
  • [LeetCode] Partition Equal Subset Sum 相同子集分割 偶数, 除以2, 或方法求解 Given anon-emptyarray containingonly positive integers, find if the array can be partitioned into two subsets such ...
  • 是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]...
  • 动态规划总结

    2020-02-24 22:19:37
    算法题型当中应该说最难的就是动态规划啊,贪心...从硬币和相等子序列问题中,发现一个trick: 如果要求数组中的个数不限:从小到大遍历(可以保证一个数可以取多次);若个数有限定:从大到小遍历(数只能取一次);...
  • 动态规划

    2021-03-14 18:05:00
    是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. class Solution { public boolean canPartition(int[] nums) { /...
  • 是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 来源:力扣(LeetCode) 链接:...
  • 动态规划】等的分隔子集 题目 问题 晓萌希望将1到N的连续整数组成的集合划分成两个子集合,且保证每个集合的数字和是相等。例如,对于N=3,对应的集合{1,2,3}能被划分成{3} {1,2}两个子集合. 这两个子集合...
  • 题目:给定n个整数(可能为负整数)组成的序列a1,a2,a3,a4,a5,..an,求该序列...该问题可以用分治法或者动态规划来求解。下面给出两种算法的思路及代码实现 2.分治法求解 思路:将所给的序列分为长度相等的两部分...
  • 给定两个数组wv, 两个数组长度相等, w[i]表示第i件商品的重量, v[i]表示第i件商品的价值。 再给定一个整数bag, 要求你挑选商品的重量加起来一定不能超 过bag, 返回满足这个条件下, 你能获得的最大价值...
  • 分割等和子集基本思想1:dfs(超时)基本思想2:动态规划 题目:416. 分割等和子集 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会...
  • 【问题描述】使用分治递归算法解最大子段问题,具体来说就是,将序列分为长度相等的左右两段,分别求出这两段的最大子段,包含左右部分子段的最大子段,求这三种情况得到的最大子段的最大值。 【输入形式】...
  • 给定一个正整数数组,问能否把其分成两个子数组,使这两个子数组的和相等。 分析:先把数组和sum求出来,题目实际上是求是否存在子数组,使该子数组的和等于sum的一半。 方法一:用sum的一半,不断减去数组中元素...
  • 题目描述 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 ...动态规划 class Solution { public boolean canPartit
  • [LeetCode] Delete Operation for Two Strings 两个字符串的删除操作 求最大子序列的长度, 然后总长度减去 2*子序列长度 ...两个字符不相等的时候就是 dp[i][j]= Math.max(dp[i-1][j], dp[i][j-1]) i个字符j...
  • 请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2: 输入:nums = [1,2,3,5] 输出:...
  • 思路: 将给定的序列分为长度相等的两段,a[1,n/2],a[n/2+1,n];1:最大子段在a[1,n/2]里面;2:最大子段在a[n/2+1,n]里面;3: 最大子段在a[i,j]里面,其中i位于(1,n/2),j位于(n/2+1,n);1,2情况直接递归求解,...
  • 首先看要求,判断是否能分成两个和相等的子集,于是我就想求出整个和的一半,然后搜索判断是不是能拼出来这样的结果,然后时间超限了。 然后就开始思考动态规划,把这个题看成0-1背包问题,当容量是整个和一半的时候...
  • 子集的动态规划DP)

    千次阅读 2018-08-25 21:19:25
    子集的 总时间限制: 1000ms 内存限制: 65536kB 描述 对于从1到N (1 &lt;= N &lt;= 71) 的连续整数集合,能划分成两个子集合,且保证每个集合的数字和是相等的。举个例子,如果N=3,对于{1,2,3}能...
  • LeetCode 416. 分割等子集(动态规划

    千次阅读 多人点赞 2020-05-19 16:07:08
    是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. ...
  • {1,2}两个子集合. 这两个子集合中元素分别的和是相等的。 对于N=3,我们只有一种划分方法,而对于N=7时,我们将有4种划分的方案。 输入包括一行,仅一个整数,表示N的值(1≤N≤39)。 输出包括一行,仅一个...
  • 如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]a[n/2:n],分别求出这两段的最大子段,则a[1:n]的最大子段有三种情形: 1)a[1:n]的最大子段与a[1:n/2]的最大子段相同; 2)a[1:n]的最大子段与a[n/2:...
  • C++动态规划算法之子集的

    千次阅读 2017-06-16 13:23:43
    子集的 题目描述 对于从1到N (1 举个例子,如果N=3,对于{1,2,3}能划分成两个子集合,他们每个的所有数字和是相等的: {3} and {1,2} 这是唯一一种分法(交换集合位置被认为是同一种划分方案,因此不会增加...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 649
精华内容 259
关键字:

动态规划和相等