1数位染色

描述
小红拿到了一个正整数 x 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。
她不知道能不能达成目标。你能告诉她吗？
输入描述：
一个正整数 x ,1≤x≤10^18
输出描述：
如果小红能按要求完成染色，输出”Yes”。否则输出”No”。

0-1背包问题
解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
#include <functional>
using namespace std;

int main() {
    long long x;
    cin>>x;
    string tmp=to_string(x);
    int n=tmp.length();
    int sum=0;
    for(auto ch:tmp){
        sum+=(ch-'0');
    }
    if(sum%2){
        cout<<"No"<<endl;
        return 0;
    }
    vector<vector<int>> memo(n,vector<int>(sum/2+1,-1));
    function<int(int,int)> dfs=[&](int i,int c)->int{
        if(i<0){
            return c==0;
        }
        int& ret=memo[i][c];
        if(ret!=-1) return ret;
        if(c<(tmp[i]-'0')){//不能选
            return ret=dfs(i-1,c);
        }
        return ret=dfs(i-1,c)+dfs(i-1,c-(tmp[i]-'0'));
    };
    if(dfs(n-1,sum/2)){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

2目标和

给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

0-1背包
解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        target+=accumulate(nums.begin(),nums.end(),0);
        if(target<0||target%2==1){
            return 0;
        }
        int m=target/=2;

        int n=nums.size();
        vector<vector<int>> memo(n,vector<int>(m+1,-1));
        function<int(int,int)> dfs=[&](int i,int c)->int{
            if(i<0) return c==0;
            int& ret=memo[i][c];
            if(ret!=-1) return ret;
            if(c<nums[i]){//不选
                return ret=dfs(i-1,c);
            }
            return ret=dfs(i-1,c)+dfs(i-1,c-nums[i]);
        };
        return dfs(n-1,m);
    }
};

3零钱兑换

描述

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，
每种面值的货币可以使用任意张， 再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.

数据范围：数组大小满足 0≤n≤10000 ， 数组中每个数字都满足 0<val≤10000， 0≤aim≤5000

要求：时间复杂度 O(n×aim) ，空间复杂度 O(aim)。

完全背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minMoney(vector<int>& arr, int aim) {
        // write code here
        int n=arr.size();
        if(n==0){
            return -1;
        }
        vector<vector<int>> memo(n,vector<int>(aim+1,-1));
        function<int(int,int)>dfs=[&](int i,int c)->int{
            if(i<0){
                return c==0?0:INT_MAX/2;
            }
            int&ret=memo[i][c];
            if(ret!=-1) return ret;
            if(c<arr[i]){
                return ret=dfs(i-1,c);
            }
            return ret=min(dfs(i-1,c),dfs(i,c-arr[i])+1);
        };
        int ans=dfs(n-1,aim);
        return ans<INT_MAX/2?ans:-1;
    }
};