动态规划——《背包问题》

474. 一和零（两种容量的0-1背包问题）

在计算机界中，我们总是追求用有限的资源获取最大的收益。

现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。

你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

状态转移方程：dp[i][j]=(dp[i-s_k_zeros][j-s_k_ones]+1, dp[i][j]);

int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector(n+1,0));
        for(string& s : strs){
            vector<int> cnt = count(s);
            int zeros=cnt[0],ones=cnt[1];

            for(int i=m;i>=zeros;i--)
                for(int j=n;j>=ones;j--){
                    dp[i][j]=max(dp[i-zeros][j-ones]+1,dp[i][j]);
                }
            }
        return dp[m][n];
    }
    vector<int> count(string& s){
        int z=0,o=0;
        for(int i=0;i<s.length();i++){
            if(s[i]=='0')z++;
            else o++;
        }
        return {z,o};
    }

494. 目标和 (背包总重可变的固定物品数量的0-1背包问题）

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

这道题基本上是自己独立思考想出来的啊哈哈哈哈哈哈

状态转移方程：dp[i][j]=max(dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]],dp[i][j]);

int findTargetSumWays(vector<int>& nums, int S) {
        int n=nums.size();
        int low=0,up=0;
        for(int i=0;i<nums.size();i++){
            low-=nums[i];
            up+=nums[i];
        }
        if(S<low||S>up)return 0;
        vector<vector<int>> dp(n,vector<int>(4020,0));
        dp[0][nums[0]+1000]++;dp[0][1000-nums[0]]++;
        for(int i=1;i<n;i++){
            for(int j=S+2000;j>=0;j--){
                if(j>=nums[i])
                    dp[i][j]=max(dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]],dp[i][j]);
                else 
                    dp[i][j]=max(dp[i-1][j+nums[i]],dp[i][j]);
            }  
        }
        return dp[n-1][S+1000];
    }

375. 猜数字大小 II

我们正在玩一个猜数游戏，游戏规则如下：

我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。

每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。

然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏

用动态规划列举猜测的所有情况，每次划分的左右两个区间内，假设正确的数字在代价更大的那个区间，找到有最小代价的划分元素。

int getMoneyAmount(int n) {
        vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        for(int len=2;len<=n;len++){
            for(int start=1;start<=n-len+1;start++){
                int mas=INT_MAX;
                for(int i=start;i<start+len-1;i++){
                    int t=i+max(dp[start][i-1],dp[i+1][start+len-1]);
                    mas=min(mas,t);
                }
                dp[start][start+len-1]=mas;
            }
        }
        return dp[1][n];
    }

待续。。。