Dynamic Programming

作者: 世界上的一道风 | 来源:发表于2019-07-03 16:53 被阅读0次

Chapter 4
18/10/2019 Lecture3: Planning by
动态语言/静态语言/动态类型语言/静态类型语言的差异
Dynamic Programming
dynamic programming
Dynamic Programming
Dynamic Programming
Dynamic programming
Dynamic Programming
Dynamic programming

动态规划

动态规划——Dynamic programming(这个词指表格)：表格用来记录子子问题的解，当求解子问题时，便可以查看。
与分治法对比：
相同点：都是通过子问题组合求解原问题
不同点：分治法将问题划分为不相交的子问题，求解再合并。动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题，此时如果用分治法就会出现重复计算求解。为了避免重复动态规划对子问题只求解一次，将其保存在表格中，从而无需每求解一个子子问题时重复计算。
我的理解：通常定义了规模为n的最优化问题，也就定义了规模小于n的最优化子问题，然后找出子问题与原问题的关联，也就是用子问题再去等价定义原来的最优化问题。

具体问题

1.钢条切割问题

具体的问题描述网上都有，就不说了。但是一些细节我说一下：
长度为n的钢条，在中间整数的部位做切割，共有 $2^{n-1}$ 种切割方案，原因如下：
切 0 刀：1种方式( $C_{n-1}^0=1$ )；
切 1 刀：中间n-1个地方选1处切， $C_{n-1}^1$ ；
切 2 刀：中间n-1个地方选2处切， $C_{n-1}^2$ ；
类推，
切 n-1 刀：中间n-1个地方选n-1处切， $C_{n-1}^{n-1}$ ；
由上，根据二项式定理（忘了看的这个博客）：
$\sum_{i=0}^mC_m^i = 2^m$
可知上述长度n的切割方案共有 $2^{n-1}$ 种。

设长度为n的钢条最优收益值为 $r_n$ ，目的是用子问题求解原问题，因此用子问题定义原问题，给出：
$r_n = max(p_n, r_1+r_{n-1},..., r_{n-1} +r_1)$
上式等价为考虑：循环求最大的该表达式：左边割下的价值加上右边的最优收益值（右边剩余为0，则 $r_0=0$ ）：
$r_n = max_{1 \le i \le n}(p_i + r_{n-i})$
伪代码如下：

# P[1,2,...,n]为长度i对应的价值
def r_n(p,n):
  if n == 0: //右边剩余为0了，返回便是
    return 0
  q = 0  
  for (i= 1 : n): //割下左边的大小为i，每个i都有一个递归调用，所以q=0在第一个比较的时候用。
    q = (q, p[i] + r_n(p, n-i));
  return q;

c++代码：

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int r_n(const vector<int> &p, const int n)
{
  if(n==0)
    return 0;
  
  int q = 0;

  for(int i = 0; i < n; ++i)
  {
    q = max(q, p[i] + r_n(p, n-1-i));
  }  

  return q;
}

int main() {
  const vector<int> prices{1,5,8,9,10,17,17,20,24,30};
  int n = prices.size();
  int ans = r_n(prices, n);
  cout << ans << endl;
}

上述递归并没有用到programming（表格）去记录值，重复计算了很多子问题的解，产生 $2^n$ 个节点的递归调用树。为分析 $r_n(p,n)$ 的运行时间，令 $T(n)$ 表示第二个参数为n时，函数 $r_n(p,n)$ 的调用次数。
$T(n) = 1 + \sum_{j=0}^{n-1}T(j)$
根节点的初次调用返回，有 $T(0)=1$ ，右边的1表示函数的第一次调用，有：

$T(n-1) = 1 + T(0) + ... + T(n-2)\\ T(n) = 1 + T(0) + ... + T(n-1)\\ T(n) - T(n-1) = T(n-1) \\ T(n) = 2T(n-1)=2^2T(n-2)=2^nT(0)=2^n\\$
所以运行运行时间是 $n$ 的指数函数。
接下来的便是利用DP优化该问题：

带备忘的自顶向下法(top-down with memoization)：特点是递归求解，但是会记录子问题的解；对应于递归树，也就是保存了树上必要的解，在其他子树遇到这个解时直接使用。
自底向上法(bottom-up method)：特点是求解一个子问题时，它的前提子问题都以求解完成，所以需要恰当定义子问题规模的概念。优点是：时间复杂性函数通常具有更小的系数。

1.伪代码：

def r_n_memo(p,n):  // 特意把一个不改变的数组r带到求解函数r_n_memo_aux中，所以新设一个外接的函数
  new r[0...n]
  for (i= 1 : n): 
    r[i] = -inf ;
  return r_n_memo_aux(p,n,r);

def r_n_memo_aux(p,n,r):
  if r[n] >= 0 :  \\ 有记录直接找到了返回
    return r[n]
  if n == 0: 
    q = 0
  else 
    q = -inf  
    for (i = 1: n): 
      q = max(q, p[i] + r_n_memo_aux(p,n-i,r));
  r[n] = q  // 关键的一步，长度n的时候，最优的价值被记录，也就是q
  return q

c++代码：

#include <iostream>
#include<vector>
#include<algorithm>
#include<climits>

using namespace std;

const int r_n_memo_aux(const vector<int> &p, const int n,vector<int> &r)
{
    int q = 0;
    if(r[n] >= 0) 
      return r[n];
    if(n == 0){
      q = 0;
    }else{
      q = INT_MIN;
      for(int i=0; i < n; ++i)
        q = max(q, p[i] +r_n_memo_aux(p,n-i-1, r));
    }
    r[n] = q;
    return q;
}

const int r_n_memo(const vector<int> &p, const int n)
{
  vector<int> r(n+1, INT_MIN); 
  return r_n_memo_aux(p, n, r);
}

int main() {
  const vector<int> prices{1,5,8,9,10,17,17,20,24,30};
  int n = prices.size();
  int ans = r_n_memo(prices, n);
  cout << ans << endl;
}

伪代码：

def bottom_r_n(p, n):
  new r[1...n] // 记录长度为i的钢条的最优值
  r[0] = 0
  for (j = 1:n) //长度为j的钢条
    q = -inf
    for (i = 1:j)
      q = max(q, p[i] + r[j-i]); //比规模为j的子问题更小的规模为i的子问题，得到规模为j的子问题的解
    r[j] = q; //记录规模为j的子问题的解
  return r[n]

c++代码：

#include <iostream>
#include<vector>
#include<algorithm>
#include<climits>

using namespace std;


const int bottom_r_n(const vector<int> &p, const int n)
{
  vector<int> r(n+1, 0);
  int q = 0;
  for(int j=0; j<n; ++j)
  {
    q = INT_MIN;
    for(int i=0; i<=j; ++i)
    {
      q = max(q, p[i] + r[j-i]);
    }
    r[j+1] = q;
  }
  return r[n];
}

int main() {
  const vector<int> prices{1,5,8,9,10,17,17,20,24,30};
  int n = prices.size();
  int ans = bottom_r_n(prices, n);
  cout << ans << endl;
}

上述两个方法的复杂度都是 $\Theta(n^2)$ 。

子问题图
- 若求子问题x的最优解时需要直接用到子问题y的最优解，那么在子问题图中就会有一条从子问题x的顶点到子问题y的顶点的有向边。
- 子问题图 $G = ( V, E )$ 的规模可以帮助我们确定DP算法的运行时间。
  1. 由于每个子问题只求解一次，因此算法运行时间等于每个子问题求解时间之和。
  2. 通常，一个子问题的求解时间与子问题图中对应顶点的度（出射边的数目）成正比，而子问题的数目等于子问题图的顶点数。
  3. 因此，DP算法运行时间与顶点和边的数量成线性关系。
重构解 : 我们可以扩展DP算法，使之对于每个问题不仅保存最优收益值，还保存对应的切割方案。利用这些信息，就能输出最优解。

extended-bottom-up-cut-rod(p, n)
1    let r[0…n] and s[0…n] be new arrays
2    r[0] = 0
3    for j=1 to n
4        q = -∞
5        for i=1 to j
6            if q < p[i]+r[j-i]
7                q = p[i]+r[j-i]
8                s[j] = i
9        r[j] = q
10    return r and s

c++代码：

#include <iostream>
#include<vector>
#include<algorithm>
#include<climits>

using namespace std;


const int bottom_r_n(const vector<int> &p, const int n)
{
  vector<int> r(n+1, 0);
  vector<int> s(n, -1);
  int q = 0;
  for(int j=0; j<n; ++j)
  {
    q = INT_MIN;
    for(int i=0; i<=j; ++i)
    {
      if(q < p[i] + r[j-i]){
        q = p[i] + r[j-i];
        s[j] = i;
      }
    }
    r[j+1] = q;
  }
  for (auto i:s)
  cout << i << " ";
  return r[n];
}

int main() {
  const vector<int> prices{1,5,8,9,10,17,17,20,24,30};
  int n = prices.size();
  int ans = bottom_r_n(prices, n);
  cout << ans << endl;
}

2.矩阵链乘法

定义：n个矩阵相乘，所需的最小标量乘法次数最少。
形式化为： $<A_1，A_2, A_3,\dots,A_n>$ ，其中矩阵 $A_i$ 的规模设为 $p_{i-1}\times p_{i}$ 。

step1: 先分析两个矩阵相乘的代价，最后一个内部的 $c_{ij}$ 的计算次数为计算代价，可以看到， $A^{p \times q}$ 乘上 $B^{q \times r}$ 的计算代价为 $pqr$ 。

Matrix-Multiply(A, B)
if A.col != B.rows
  error "incompatible dimensions"
else let C be a new [A.rows,B.cols] matrix
for i = [1,...,A.rows]:
  for j = [1,...,B.cols]:
   c_{ij} = 0
   for k = [1,...,A.cols]:
    c_{ij} = c_{ij} + A[i][k] * A[k][j]
return C

step2: 找到最优子结构,然后用子问题定义原问题。设 $m[i,j]$ 表示计算矩阵 $\{A_1,A_2,...,A_j\}$ 所需要的标量乘法次数的最小值，可以得到：

$m[i,j] = 0 ， i=j \\ m[i,j] = m[i,k] + m[k+1,j] + p_{i-1}p_kp_j ， i < j$
step3: 每一次高层的运算，都会调用底层结果，越是底层，被调用的次数越多。所以可以采用自底向上的方法，先对底层逐个求解，当上层需要调用底层时，底层已经被求解完毕。
自低向下计算最低代价C++代码（多生成的0行0列不使用，免得搞不清楚这个计算次序）：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

vector<vector<unsigned int>> matrix_chain_order(const vector<int> &p,vector<vector <int>> &s)
{
  int n = p.size()-1;
  vector<vector<unsigned int>> m(n+1, vector<unsigned int>(n+1, 0));
  for(int i =1; i<=n; ++i)
    m[i][i] = 0;
  
  for (int l=2; l<=n; ++l) // 
    for (int i=1; i<=n-l+1; ++i)
    {
      int j = i+l-1;
      m[i][j] = INT_MAX;
      for (int k=i; k<=j-1; ++k)
      {
        int q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
        if (q < m[i][j])
        {
          m[i][j] = q;
          s[i][j] = k;
        }
      }
    }
  return m;
}


void print(const vector<vector <int>> &s, int i, int j)
{
  if (i == j)
    cout << "A" << i;
  else{
    cout << "(";
    print(s, i, s[i][j]);
    print(s, s[i][j]+1, j);
    cout << ")";
  }
}

int main() {
  const vector<int> p{30,35,15,5,10,20,25};
  vector<vector<unsigned int>> ans;
  int n = p.size()-1;
  vector<vector <int>> s(n+1, vector<int>(n+1, 0));
  ans = matrix_chain_order(p, s);
  for(int i =0 ; i < ans.size(); ++i)
  {
    for(int j=0; j<ans[0].size(); ++j)
      cout << ans[i][j] << " ";
    cout << endl;
  }
  cout << ans[1][p.size()-1] << endl;

  print(s,1, 6);

}


// results:
0 0 0 0 0 0 0
0 0 15750 7875 9375 11875 15125
0 0 0 2625 4375 7125 10500
0 0 0 0 750 2500 5375
0 0 0 0 0 1000 3500
0 0 0 0 0 0 5000
0 0 0 0 0 0 0
15125
((A1(A2A3))((A4A5)A6))

如图：上面的公式为什么i、l、j绕来绕去，就是为了首先计算主对角线贴着的数m[i][j]，然后才能往上继续算：

image.png

带备忘的计算方法（自顶向下），为每个子问题维护一个表项来保存它的解。书上的伪代码比自底向上更符合直觉：

#include <iostream>
#include<vector>
#include<climits>
using namespace std;

int matrix_chain_order(vector< vector<unsigned int>> &m,const vector<int> &p,int i, int j)
{
  if (m[i][j] < INT_MAX)
    return m[i][j];
  
  if (i == j)
  {
    m[i][j] = 0;
  }else{
    for (int k=i; k<=j-1; ++k)
    {
      int q = matrix_chain_order(m,p,i,k) + matrix_chain_order(m,p, k+1, j) + p[i-1] * p[k] * p[j];
      if (q < m[i][j]) 
        m[i][j] = q;
    }
  }
  return m[i][j];
}


int main() {
    const vector<int> p{30,35,15,5,10,20,25};
    int ans;
    int n = p.size()-1;
    vector<vector <unsigned int>> s(n+1, vector<unsigned int>(n+1, INT_MAX));
    ans = matrix_chain_order(s, p,1, n);
    cout << ans << endl;
}

3. 最常公共子序列(LCS)

子序列的概念：一个给定的子序列，就是将给定序列中零个或多个元素去掉后得到的结果。
给定两个序列 $X=<x_1,....x_n>$ 和 $Y=<y_1,....,y_n>$ ，求 $X$ 和 $Y$ 的最长公共子序列。

根据书上的LCS定理，定义 $C[i,j]$ 表示 $X_i$ 和 $Y_j$ 的LCS长度，也就是说，还是用二维数组记录子问题的解：
$C_{i,j} = 0， if : i=0 \bigvee j=0 \\ C_{i,j} = C_{i-1,j-1} +1 ，if : i,j > 0 \bigwedge x_i = y_j \\ C_{i,j} = max(C_{i,j-1}， C_{i-1, j}) ， if : i,j > 0 \bigwedge x_i \neq y_j$

根据LCS的最优子结构定理，给出计算的c++代码，运行时间为 $\Theta(mn)$ , $m、n$ 为子序列的长度：

#include <iostream>
#include<vector>
#include<string>
#include<climits>
using namespace std;

void LCS(const string &a, const string &b, vector<vector<int>> &ans, vector<vector<int>> &path)
{

  int m = a.size();
  int n = b.size();
  vector<vector<int>> _ans(m+1,vector<int>(n+1, 0));
  vector<vector<int>> _path(m+1,vector<int>(n+1, 0));
  for(int i=1; i<=m; ++i)
    for(int j=1; j<=n; ++j)
    {
      if(a[i-1] == b[j-1])
      {
        _ans[i][j] = _ans[i-1][j-1] + 1;
        _path[i][j] = 13;
      }else if(_ans[i-1][j] >= _ans[i][j-1])  //没有这个等于号，path会出错
        {
          _ans[i][j] = _ans[i-1][j];
          _path[i][j] = 1;
        }else{
          _ans[i][j] = _ans[i][j-1];
          _path[i][j] = 3;
        }
    }
  ans = _ans;
  path = _path;
}

void print(const vector<vector<int>> &path, const string &a, int i, int j)
{
  if (i==0 || j==0)
    return;
  if (path[i][j]==13)
  {
    print(path, a, i-1, j-1);
    cout << a[i-1];
  }else if(path[i][j] == 1)
  {
    print(path,a, i-1, j);
  }else
  {
    print(path, a, i, j-1);
  }
}
// 上下左右分别用1234代替，所以左上用13表示；
// 左表示往左回溯，上表示向上回溯，左上表示相等，是属于最长公共序列的字符位置。
int main() {
    vector<vector<int>> ans, path;
    string a={"ABCBDAB"};
    string b={"BDCABA"};
    LCS(a,b, ans, path);
    cout << "answer is : " << endl;
    for (int i=0; i<ans.size(); ++i)
    {
      for (int j=0; j<ans[0].size(); ++j)
        cout << ans[i][j] << " ";
      cout << endl;
    }
     cout << "path is : " << endl;
    for (int i=0; i<path.size(); ++i)
    {
      for (int j=0; j<path[0].size(); ++j)
        cout << path[i][j] << " ";
      cout << endl;
    }
    print(path, a, a.size(), b.size());

}

answer is :
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 1 1 1 1 2 2
0 1 1 2 2 2 2
0 1 1 2 2 3 3
0 1 2 2 2 3 3
0 1 2 2 3 3 4
0 1 2 2 3 4 4
path is :
0 0 0 0 0 0 0
0 1 1 1 13 3 13
0 13 3 3 1 13 3
0 1 1 13 3 1 1
0 13 1 1 1 13 3
0 1 13 1 1 1 1
0 1 1 1 13 1 13
0 13 1 1 1 13 1
BCBA

效果图，也是需要从左上角计算到右下角，返回答案。

最优二叉搜索树

定义：给定n个不同关键字的已排序的序列 $K=<k_1,k_2,....,k_n>$ ，用它们构造一颗二叉搜索树，每一个关键字 $k_i$ 都有一个对应的搜索概率 $p_i$ ，搜索失败的位置 $d_0,d_1,....,d_n$ （称为伪关键字）也有对应的搜索概率 $q_i$ 。每次搜索要么成功，要么失败，希望构建的二叉树T的搜索代价期望最小，T便是最优的二叉搜索树。
step 1: 最优二叉搜索树 $T$ 的子树 $T^i$ 必然也是最优的二叉搜索树，不然反推 $T$ 也不是最优的;
step 2: 假设子树 $T^i$ 包含关键字 $k_i,...,k_j$ ，当选择 $k_i$ 为根节点时，左子树不包含实际的关键字（k），但是包含伪关键字 $d_{i-1}$ ;
step3: 递归定义：求解包含关键字 $k_i,....,k_j$ 的最优二叉搜索树，其中 $i\ge{1}$ and ${i-1} \le j \le n$ ；
定义 $e_{i,j}$ 为包含关键字 $k_i,...,k_j$ 的最优二叉搜索树中进行一次搜索的期望代价。因此我们希望计算的是 $e_{1, n}$ 。

根据书上的公式15.11，对于包含 $k_i,...,k_j$ 的子树，选择一个节点作为根节点，其他节点作为它的子树，其节点的深度都加1，所以提出来便是下面的公式，也就是其他节点的期望代价为：
$w(i,j) = \sum_{l=i}^jp_l + \sum_{l=i-1}^j q_l$
由此，设 $k_r$ 为根节点，有：
$e_{i, j}=p_r + e_{i, r-1} + e_{r+1, j} + w(i,r-1) + w(r+1,j)$
$w(i,j)$ 表示的是其中某节点成为根节点，这里选 $r$ ,其他左边两边递归的定义如下：
$w(i,j) = p_r + w(i,r-1) + w(r+1,j)$

因此：
$e_{i, j} = e_{i,r-1} + e_{r+1, j} + w(i,j)$
最终的递归式为：
$e_{i,j} = q_{i-1} , if : j= i-1\\ e_{i,j} = \min_{i\le r \le j}(e_{i,r-1} + e_{r+1, j} + w(i,j)) , if : j \ge i$

c++代码：

#include <iostream>
#include <vector>
#include <string>
#include<climits>
using namespace std;

void optimal_BST(const vector<float> &p,const vector<float> &q, vector<vector<float>> &ans, vector<vector<int>> &path)
{
  const int n = p.size()-1; // 有效节点数目
  vector<vector<int>> _path(n+1, vector<int>(n+1, -1));
  vector<vector<float>> _ans(n+2, vector<float>(n+1, 0.0));
  vector<vector<float>> _aux(n+2, vector<float>(n+1, 0.0));

  //init 
  for (int i=1; i<=n+1; ++i)
  {
        _ans[i][i-1] = q[i-1];
        _aux[i][i-1] = q[i-1];
  }

  for (int l=1; l<=n; ++l)
  {
    for (int i=1; i<=n-l+1; ++i) // n-l+1为对角线上位置元素长度
    {
      int j = i + l -1;  // 随着i、l变化，目的是紧跟已计算的下方来计算目前位置
      _ans[i][j] = INT_MAX+0.0;
      _aux[i][j] = _aux[i][j-1] + p[j] + q[j];

      for (int r=i; r<=j; ++r)
      {
        float t = _ans[i][r-1] + _ans[r+1][j] + _aux[i][j];
        if (t < _ans[i][j])
        {
          _ans[i][j] = t;
          _path[i][j] = r;
        }
      }
    }
  }
  ans = _ans;
  path = _path;
}



void construct_BST(const vector<vector<int>> &path, int row, int col)
{

  if (row <= col)
  {
    int root = path[row][col];
    cout << root << " ";
    construct_BST(path, row, root-1);
    construct_BST(path, root+1, col);
  }
}
int main() {
  vector<float> p={-10000,0.15,0.10,0.05,0.10,0.20};
  vector<float> q={0.05,0.10,0.05,0.05,0.05,0.10};
  vector<vector<float>> ans;
  vector<vector<int>> path;
  optimal_BST(p, q, ans, path);
  for(int i=0; i<ans.size();++i)
  {
    for (int j=0; j<ans[0].size(); ++j)
      cout << ans[i][j] << "  ";
    cout << endl;
  }
  cout << "path is : ";
  int n = p.size()-1;
  construct_BST(path, 1, n); //因为第0行也是没有用的辅助行，所以从1开始。

}

0  0  0  0  0  0
0.05  0.45  0.9  1.25  1.75  2.75
0  0.1  0.4  0.7  1.2  2
0  0  0.05  0.25  0.6  1.3
0  0  0  0.05  0.3  0.9
0  0  0  0  0.05  0.5
0  0  0  0  0  0.1
path is : 2 1 5 4 3

图示的解答：e对应ans矩阵，w对应辅助矩阵，root对应path矩阵。总是用二维数组完成子问题的记录，提高效率。

image.png

2. 背包问题

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
//背包问题：n个重量为w_1,w_2...w_n的物品，价值分别为：v_1,v_2,...,v_n.
// 背包最大承重为M，可装多少个物品使得价值最大？

//dynamic programming: F(i, j):表示取出前i个物品，背包重量为j，其最大的价值。

// F(i -1, j) 是少一个物品且能背进包，但价值最优的值。
// F(i, j) =  1.Max( F(i-1,j), v_i + F(i-1, j - w_i)) , j - w_i >= 0
// F(i, j) =  2. F(i-1, j) , j - w_j < 0
// init: F(0, j) = 0 for j >= 0 , F(i, 0) = 0 for i >= 0;


class Package
{
  public:
  int F();
  bool init(const int i,const int j);
  void show();
  private:
  int _row=0, _col=0;
  
  vector<vector<int>> _obj; 
  vector<vector<int>> _table;
};

void Package::show()
{
  for (int row=0; row<_row; ++row)
  {
    for (int col=0; col<_col; ++col)
    {
      cout << _table[row][col]<< ' ';
    }
    cout << endl;
  }
}
bool
Package::init(const int i,const int j)
{
  _row = i;
  _col = j;
  
  _table.resize(_row);
  for (int row=0; row < _row; ++row)
  {
    _table[row].resize(_col);
  }

  _table[0].assign(_col, 0);

  _obj.resize(2);
  int weight=0, value=0;
  while ((cin >> weight) && (weight > 0))
  {
    cin >> value;
    _obj[0].push_back(weight);
    _obj[1].push_back(value);
  }
  
  for (int row=0; row<2; ++row)
  {
    for (int col=0; col<_obj[row].size(); ++col)
    {
      cout << _obj[row][col] << ' ';
    }
    cout << endl;
  }
  
  return true;
}


int
Package::F()
{
  int maxnum = 0;
  cout << "row is : " << _row << " col is : " << _col << endl;
  for( int row=1; row<_row; ++row )
  {
    // 递推式
    for(int col=1; col<_col; ++col)
    { 
      if((col - _obj[0][row] > 0)){
        maxnum = max(maxnum, max(_table[row-1][col], _obj[1][row-1] + _table[row-1][col-_obj[0][row-1]]));
      }else{
        maxnum = max(maxnum, _table[row-1][col]);
      }
      cout << row << " " << col << " " << maxnum << endl;
      _table[row][col] = maxnum;
    }
  }
  // cout<< _table[_row-1][_col-1]<< "Fuck .." << endl;
  return _table[_row-1][_col-1];
}


int main() {
  //input: weight - value： 2 - 12, 1-10， 3-20，2-15.
  // input negtive value to stop cin flow.
  // ans: 37
  Package pac;
  int ans;
  if(pac.init(5, 6))
  {
    ans = pac.F();
    pac.show();
    cout << " answer is : " << ans << endl;
  }
  return 0;
}

如：


clang version 7.0.0-3~ubuntu0.18.04.1 (tags/RELEASE_700/final)
 clang++-7 -pthread -o main main.cpp
 ./main
2
12
1
10
3
20
2
15
-1
2 1 3 2
12 10 20 15
row is : 5 col is : 6
1 1 0
1 2 12
1 3 12
1 4 12
1 5 12
2 1 12
2 2 12
2 3 12
2 4 22
2 5 22
3 1 22
3 2 22
3 3 22
3 4 32
3 5 32
4 1 32
4 2 32
4 3 37
4 4 37
4 5 37
0 0 0 0 0 0
0 0 12 12 12 12
0 12 12 12 22 22
0 22 22 22 32 32
0 32 32 37 37 37
 answer is : 37

Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

class Solution {
public:
    // F(I, W):可以取前I种硬币，价值为W，可以有F(I,W)种取法；
    // F(I, W) = sum_n F(I-1, W - n*W_i) , n=1,2,3... W-n*W_i > 0
    // F(I, W) = sum_n F(I-1, W - n*W_i) + 1, n=1,2,3... W-n*W_i >= 0
    // F(I, W) = 0, n=1,2,3... W-n*W_i < 0
    int change(int amount, vector<int>& coins) {
        
        if(amount <= 0) return 1;
        if (coins.size() == 0 ) return 0;
        vector<vector<int>> mat(coins.size(), vector<int>(amount+1));
        //
        for (int idx=0; idx< coins.size(); ++idx)
        {
            mat[idx][0] = 1;
        }
        
        for (int value=1; value < amount + 1; ++value)
        {
            if ((value % coins[0])==0)
                mat[0][value] = 1;
        }
        
        // 前num种类的硬币数目
        for(int num=1; num < coins.size(); ++num)
        {
            
            for (int col=1; col < amount+1; ++col)
            {
                unsigned int tmp = 0;
                int W = col;
                int W_i = coins[num];
            
                for (int i_step=0; i_step<100000000; ++i_step)
                {
                    if ((W - i_step * W_i) >= 0){
                        tmp += mat[num-1][W- i_step * W_i];
                    }else{
                        break;
                    }
                }
                mat[num][W] = tmp;
            }    
        }
        //display(mat);
        return mat[coins.size()-1][amount];
        
    }

private:
    void display(vector<vector<int>> &mat)
    {
        for (int row=0; row<mat.size(); ++row)
        {
            for(int col=0; col<mat[0].size(); ++col)
            {
                cout << mat[row][col] << ' ';
            }
            cout << endl;
        }
    }
};

考虑只记录一行，逐渐更新每一行，因为硬币面额是不一样的，每次价格递增也不一样，所以每次更新是惟一的：

class Solution {
public:
    unsigned long long change(int amount, vector<int>& coins) {
        vector < unsigned long long > dp(amount+1);
        dp[0] = 1;
        for(int x : coins){
            for(int i = 1 ; i <= amount ; i++)
                if(i-x >=0)
                    dp[i] += dp[i-x];
        }
        return dp[amount];
    }
};

Chapter 4
Chapter 4: Dynamic Programming Dynamic programming comput...
18/10/2019 Lecture3: Planning by
Planning by Dynamic Programming Dynamic Programming 具有某种时...
动态语言/静态语言/动态类型语言/静态类型语言的差异
动态语言(dynamic programming language): programming behaviors...
Dynamic Programming
研究生学过DP，当时觉得还挺简单的，就是从初始状态开始，找到推导公式一步步往下推嘛。但实际刷题时发现DP还是很难的...
dynamic programming
本质：记忆化搜索避免重复计算多重循环vs记忆化搜索多重循环：可以不用递归可以对空间复杂度进行优化步骤：初...
Dynamic Programming
planning all the time.Find a polynomial time. 动态规划背后的基本思想...
Dynamic Programming
70. Climbing Stairs : Easy198. House Robber : Easy121. ...
Dynamic programming
本文针对两篇优秀动态规划文章中存在的不易理解的部分：状态、状态转移的定义和状态转移方程的编程实现部分进行个人解读。...
Dynamic Programming
DP 基本有两个模板：自上而下：先有最初的结果，求出最后的结果。自下而上：先有最后的结果，然后求出最初的结果...
Dynamic programming
Today, I'm going to talk something detailed about dynamic...

Dynamic Programming

动态规划

具体问题

1.钢条切割问题

2.矩阵链乘法

3. 最常公共子序列(LCS)

最优二叉搜索树

2. 背包问题

Coin Change 2

相关文章

Chapter 4

18/10/2019 Lecture3: Planning by

动态语言/静态语言/动态类型语言/静态类型语言的差异