动态编程：搭建桥梁

在本教程中，我们将在DP的帮助下解决建筑桥梁的问题。这是一个经典的DP问题。

问题陈述：

在给定一条河的情况下，您需要以跨河的方式建造一座桥，这样，只有给定的一对人才能形成桥，并且任何桥都不应相互交叉。

例如，给定点[1，2] [5，4] [8，10]，可以按以下方式形成桥：

下面的桥无效

上面的桥是无效的，因为桥[10，6]相交[8，10]。

顶部是北座标；底部是南坐标。

因此，根据给定的问题，您将获得一对，并且您需要通过满足上述条件来构建最大数量的桥。

我们将借助DP和最长的公共子序列来解决此问题。

此问题可以通过以下步骤解决：

1. 将南坐标按升序排序。
2. 找出最长的北坐标子序列
3. 加入最长递增子序列中的桥。

例：

考虑如下坐标：

步骤1：根据南座标排序

步骤2：找出最长的递增子序列

在这里，排序顺序是最长的递增子序列。

与原始的最长增加子序列算法进行比较时，变化很小。

即在原始算法中，只有下一个元素更大时，我们才选择该元素。但是这里我们也选择元素是否相等。

C ++解决方案

#include <iostream> 
  
using namespace std; 
  
// north-south bridge co-ordinates 

struct bridge_co_ordinates
{ 
    int north, south; 
}; 
  
// comparison function to sort bridge co ordinates
bool compare(struct bridge_co_ordinates a, struct bridge_co_ordinates b) 
{ 
    if (a.south == b.south) 
        return a.north < b.north; 
    return a.south < b.south; 
} 
  

int get_max_bridges(struct bridge_co_ordinates values[], int n) 
{ 
    int dp_array[n]; 
    for (int i=0; i<n; i++) 
        dp_array[i] = 1; 
          
    sort(values, values+n, compare); 
      
    // logic of longest increasing subsequence applied 上  the north coordinates 
    for (int i=1; i<n; i++) 
        for (int j=0; j<i; j++) 
            if (values[i].north >= values[j].north  
                && dp_array[i] < 1 + dp_array[j]) 
                dp_array[i] = 1 + dp_array[j]; 
          
          
    int max = dp_array[0]; 
    for (int i=1; i<n; i++) 
        if (max < dp_array[i]) 
            max = dp_array[i]; 
             
    return max;         
} 
  

int main() 
{ 
    struct bridge_co_ordinates values[] = {{3, 5}, {2, 4}, {2, 5}, {1, 2}}; 
    int n = 4; 
    cout << "Maximum number of bridges = " << get_max_bridges(values, n);     
    return 0; 
}

输出：

Maximum number of bridges = 4

该网站上可用的教程列表：