1.0-1背包

设计一个动态规划算法，通常可按照以下几个步骤进行：
(1) 找出最优解的性质，并刻画其结构特征。
(2) 递归地定义最优解的值
(3) 以自底而上的方式计算出最优值
(4) 根据计算最优值时得到的信息，构造一个最优解。

对于一个给定的问题，若具有以下两个性质，则可以考虑用动态规划法来求解。

(1) 最优子结构。如果一个问题的最优解中包含了其子问题的最优解，就说该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划法可能会适用，但是此时贪心策略可能也是适用的。

(2) 重叠子问题。指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说该问题包含重叠子问题。此时若用分治法递归求解，则每次遇到子问题都会视为新问题，会极大地降低算法的效率，而动态规划法总是充分利用重叠子问题，对于每个子问题仅计算一次，把解保存在一个在需要时就可以查看的表中，而每次查表的时间为常数。

问题：有n个物品，第i个物品价值为vi，重量为wi，其中vi和wi均为非负数，背包的容量为W，W为非负数。现需要考虑如何选择装入背包的物品，使装入背包的物品总价值最大。该问题以形式化描述如下：

目标函数为：

约束条件为：

满足约束条件的任一集合（x1，x2，…，xn）是问题的一个可行解，问题的目标是要求问题的一个最优解。考虑一个实例，假设n=5，W=17， 每个物品的价值和重量如表9-1所示。可将物品1，2和5装入背包，背包未满，获得价值22，此时问题解为你（1，1，0，0，1）。也可以将物品4和5装入背包，背包装满，获得价值24，此时解为（0，0，0，1，1）。

下面根据动态规划的4个步骤求解该问题。

(1) 刻画0-1背包问题的最优解的结构。

可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果一个问题的最优解包含了物品n，即xn=1，那么其余x1，x2，…，x(n-1)一定构成子问题1，2，…，n-1在容量W-wn时的最优解。如果这个最优解不包含物品n，即xn=0，那么其余x1，x2，…，x(n-1)一定构成子问题1，2，…，n-1在容量W时的最优解。

(2)递归定义最优解的值

根据上述分析的最优解的结构递归地定义问题最优解。设c[i,w]表示背包容量为w时，i个物品导致的最优解的总价值，得到下式。显然要求c[n,w]。

(3)计算背包问题最优解的值

(4)根据计算的结果，构造问题最优解。

根据上一步计算的c数组，很容易构造问题的最优解。判断c[i,w]与c[i-1,w]的值是否相等，若相等，则说明xi=0，否则为1。

#include <iostream>
#include <vector>

using namespace std;

void output_vec(vector<int> vec)
{
    if(vec.empty())
        return;
    else
    {
        for (int i = 0; i < vec.size(); i++)
        {
            cout << vec[i] << " ";
        }
        cout << endl;
    }
}

//使用动态规划得到递归解的值
void DP(vector<vector<int>>& cost, const int N, const int W, const vector<int> weight, const vector<int> value)
{
    for (int i = 1; i <= N; i++)
    {
        cost[i][0] =  0;
        for (int w = 1; w <= W; w++)
        {
            if (weight[i-1] > w)
            {
                cost[i][w] = cost[i-1][w];
            } 
            else
            {
                int tmp = cost[i-1][w -weight[i-1]] + value[i-1];
                if(cost[i-1][w] > tmp)
                    cost[i][w] = cost[i-1][w];
                else
                    cost[i][w] = tmp;
            }
        }
    }
}


//自下而上得到result
void findPath(vector<vector<int>> cost, int N, int W, vector<int> weight, vector<int>& result)
{
    int w = W; //用于记录重量

    for (int i = N; i >= 2; i--)
    {
        if (cost[i][w] == cost[i-1][w])
        {
            result[i-1] = 0;
        } 
        else
        {
            result[i-1] = 1;
            w -= weight[i-1];
        }
    }

    if(cost[1][w] == 0)
        result[0] = 0;
    else
        result[0] = 1;
}

int main()
{
    int N = 5;   //物品数
    int W = 17;  //最多可以容纳的重量
    int w[] = {3, 4, 7, 8, 9};    //每个物品的重量
    int v[] = {4, 5, 10, 11, 13}; //每个物品的价值量

    vector<int> weight(w,w+N);   //利用数组给vector赋值
    vector<int> value(v,v+N);

    vector<vector<int>> cost(N+1);  //加1是为了cost下标可以从1开始
    for (int i = 0; i < N+1; i++)
        cost[i].resize(W+1);

    DP(cost,N,W,weight,value);

    vector<int> result(N);

    findPath(cost,N,W,weight,result);

    cout << "N : " << N << endl;

    cout << "W : " << W << endl;

    cout << "weight : ";
    output_vec(weight);

    cout << "value : ";
    output_vec(value);

    cout << "Result : ";
    output_vec(result);

    return 0;
}

2.连续子数组最大的和

充分利用了题目的特性。算法时间复杂度O(n)。

int max_sub_array(int a[],int low, int high)
{
    int sum = numeric_limits<int>::min(); //定义无穷小
    int cur_sum = 0;

    for(int i = low; i <= high; i++)
    {
        if (cur_sum > 0)
        {
            cur_sum += a[i];
        }
        else
        {
            cur_sum = a[i];
        }

        if (cur_sum > sum)
            sum = cur_sum;
    }

    return sum;
}

3.Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

分析：设状态为f[i][j]，表示从起点（0,0）到达（i，j）的最小路径和，则状态转移方程为f[i][j] = min(f[i-1][j]，f[i][j-1]) + grid[i][j]

Solution：

int minPathSum(vector<vector<int>> &grid)
{
    if(grid.size() == 0)
        return 0;

    const int m = grid.size();    //行
    const int n = grid[0].size(); //列
    int i,j;

    vector<vector<int>> f(m);
    for(i = 0; i < m; i++)
        f[i].resize(n);


    f[0][0]  = grid[0][0];

    for(i = 0; i < m; i++)
        f[i][0] = f[i-1][0] + grid[i][0];

    for (i = 0; i < n; i++)
        f[0][i] = f[0][i-1] + grid[0][i];

    for(i = 1; i < m; i++)
    {
        for(j = 1; j < n; j++)
        {
            f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i][j];
        }
    }

    return f[m-1][n-1];
}

4.Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

Solution：

int maxRect(vector<vector<char>>& matrix)
{
    if(matrix.size() == 0)
        return 0;

    const int m = matrix.size();
    const int n = matrix[0].size();
    vector<int> H(n,0); //高
    vector<int> L(n,0); //左
    vector<int> R(n,n); //右

    int ret = 0;
    int i,j;

    for (i = 0; i < m; i++)
    {
        int left = 0,right = n;

        //calculate L(i,j) from left to right
        for (j = 0; j < n; j++)
        {
            if(matrix[i][j] == ‘1‘)
            {
                H[j]++;
                L[j] = max(L[j],left);
            }
            else
            {
                left = j+1;
                H[j] = 0;
                L[j] = 0;
                R[j] = n;
            }
        }

        //calculate R[i,j] from right to left
        for(j = n-1; j >= 0; j--)
        {
            if(matrix[i][j] == ‘1‘)
            {
                R[j] = min(R[j],right);
                ret = max(ret, H[j]*(R[j]-L[j]));
            }
            else
            {
                right = j;
            }
        }
    }

    return ret;
}

5.Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Solution：

   int maxProfit(vector<int>& prices) 
   {  
       if(prices.size()<=1)  
           return 0;  
       int curMin=prices[0];  
       int maxProfit=0;  
       for(int i=1;i<prices.size();i++)  
       {  
           maxProfit=max(maxProfit,prices[i]-curMin);  
           curMin=min(curMin,prices[i]);//获得历史最小价格的股票  
       }  
       return maxProfit;  
   }  

6.Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

分析：

Solution：

int maxProfit(vector<int>& price)
{
    if(price.size() < 2)
        return 0;

    const int n = price.size();
    int i;
    vector<int> f(n,0);
    vector<int> g(n,0);

    int valley = price[0];
    for(i = 1; i < n; i++)
    {
        valley = min(valley, price[i]);
        f[i] = max(f[i-1], price[i]-valley);
    }

    int peak = price[n-1];
    for (i = n-2; i >=0; i--)
    {
        peak = max(peak, price[i]);
        g[i] = max(g[i], peak-price[i]);
    }

    int max_profit = 0;
    for (i = 0; i < n; i++)
        max_profit = max(max_profit, f[i]+g[i]);

    return max_profit;
}

7.Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = “leetcode”,
dict = [“leet”, “code”].

Return true because “leetcode” can be segmented as “leet code”.

分析：

Solution：

时间复杂度O（n^2）,空间复杂度O（n）

bool wordBreak(string s, unordered_set<string>& dict)
{
    //长度为n的字符串有n+1个隔板
    vector<bool> f(s.size()+1, false);
    f[0]  = true;
    for (int i = 1; i <= s.size(); i++)
    {
        for (int j = i-1; j >= 0; j--)
        {
            if (f[j] && dict.find(s.substr(j,i-j)) != dict.end())
            {
                f[i] = true;
                break;
            }
        }
    }
    return f[s.size()];
}

8.Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = “catsanddog”,
dict = [“cat”, “cats”, “and”, “sand”, “dog”].

A solution is [“cats and dog”, “cat sand dog”].

Solution：

时间复杂度O（n^2）,空间复杂度O（n^2）

vector<string> wordBreak(string s, unordered_set<string>& dict)
{
    //长度为n的字符串有n+1个隔板
    vector<bool> f(s.length()+1, false);

    //prev[i][j]为true，表示s[j,i)是一个合法单词，可以从j处分开
    //第一行未用
    vector<vector<bool>> prev(s.length()+1, vector<bool>(s.length()));
    f[0] = true;
    int i,j;

    for (i = 1; i <= s.length(); i++)
    {
        for (j = i-1; j >=0; j--)
        {
            if(f[j] && dict.find(s.substr(j,i-j) != dict.end()))
            {
                f[i] = true;
                prev[i][j] = true;
            }
        }
    }

    vector<string> result;
    vector<string> path;
    gen_path(s, prev, s.length(), path, result);
    return result;
}

//DFS遍历树，生成路径
void gen_path(const string &s, const vector<vector<bool>>& prev, int cur, vector<string>& path, vector<string>& result)
{
    if (cur == 0)
    {
        string tmp;
        vector<string>::iterator iter;
        for(iter = path.begin(); iter != path.end(); iter++)
            tmp += *iter + " ";
        tmp.erase(tmp.end()-1);
        result.push_back(tmp);
    } 
    else
    {
        for (int i = 0; i < s.size(); i++)
        {
            if (prev[cur][i])
            {
                path.push_back(s.substr(i,cur-i));
                gen_path(s,prev,i,path,result);
                path.pop_back();
            }
        }
    }
}