ue 抗鋸齒 渲染序列失靈

Problem statement:

問題陳述：

Given a square matrix of size n x n, find the sum of the Zigzag sequence with the largest sum. A zigzag sequence starts from the top and ends at the bottom. Two consecutive elements of sequence cannot belong to the same column.

給定大小為nxn的方陣， 找到Zigzag序列的總和最大 。 之字形序列從頂部開始，在底部結束。 序列的兩個連續元素不能屬于同一列。

    Input:
First line contains an integer N denoting the size of the matrix. 
Then in the next line are N*N space separated values of the matrix.
Output:
Print the required max sum.
Constraints:
1<=N<=100
1<=M[][]<=1000

Example:

例：

    Input:
Input matrix
3 8 2
4 8 5
6 9 7
Output: 22
Maximum Zigzag sequence is: 
8->5->9
Other sequences can be: 
3->8->6 etc.
Input:
Input matrix
3  2  1
10 8  5 
6  6  4
Output: 18
In the above also, the maximum zigzag sequence will be:
2->10->6

The second example clearly shows that the greedy solution wouldn't work. Let's say we opt for greedy technique and as a measure, what we do is to extract local maximum, i.e., to extract maximum out of this row and the go-ahead to the next row and find out maximum skipping the column where we found our last maximum.

第二個例子清楚地表明，貪婪的解決方案是行不通的。 假設我們選擇貪婪技術，并且作為一種度量，我們要做的是提取局部最大值，即從該行中提取最大值，然后繼續到下一行，并找出最大值，跳過找到我們的列最后的最大值。

So if we follow a similar approach, let's check what we can lead to.

因此，如果我們采用類似的方法，那么讓我們檢查一下會導致什么。

So, firstly, we will pick 3 out of the first row (0^th row)

因此，首先，我們將從第一行( ^第 0行)中選擇3 ^個

From the next row, we will pick 8 as we can't peek 10 due to out constraint.

在下一行中，我們將選擇8 ，因為由于出局限制我們無法窺視10 。

And from the next row, we will pick 6?(of 0^th column)

然后從下一行中，選擇6 ( ^第 0列)

So it sums up to 3+8+6 which is 17. But it's wrong we know output would be 18. So finding local best doesn't lead to global best. Hence, greedy will not work here.

因此，總和為3 + 8 + 6 ，即17 。 但是我們知道輸出為18是錯誤的。 因此，找到本地最佳并不能帶來全球最佳。 因此，貪婪在這里不起作用。

We need dynamic programing or recursion to solve.

我們需要動態編程或遞歸來解決。

Solution Approach:

解決方法：

So, let's see what can be a recursive solution. Then, we will check for overlapping sub-problems and will gradually optimize the recursion by memorization.

因此，讓我們看看什么是遞歸解決方案。 然后，我們將檢查重疊的子問題，并通過記憶逐步優化遞歸。

Let the recursive function be, recurZigzag(matrix, cur_row, cur_colulm, n)

設遞歸函數為recurZigzag(matrix，cur _row ，cur _colulm ，n)

    Function recurZigzag(matrix,currow,curcolulm):
If (currow reaches n)
Return 0;
for i=0 to n except curcolumn
Return  matrix[currow][curcolumn] + max(recurZigzag(matrix, currow + 1, i))
End Function
// In the main function
for column=0 to n-1
result=max?(result,recurZigzag(matrix,0,column)

So what we did?

那我們做了什么？

We are starting from each column on the top row.

我們從第一行的每一列開始。

Then we are recursively checking for the next row skipping the current column. So, this checks all combinations possible.

然后，我們遞歸地檢查跳過當前列的下一行。 因此，這將檢查所有可能的組合。

I would recommend to create the recursion tree for example 1 and check whether you can find overlapping sub-problems. There will be a lot of overlapping problems even for smaller inputs.

我建議為示例1創建遞歸樹，并檢查是否可以找到重疊的子問題。 即使對于較小的輸入，也會有很多重疊的問題。

So, we need to pass that overhead and we can solve that by memorization technique where we store the value of solved sub-problem in DP[][]

因此，我們需要傳遞該開銷，并且可以通過存儲將已解決子問題的值存儲在DP [] []中的記憶技術來解決該問題。

So, we first lookup in DP[][] whether it's already solved or not. If it's already solved then we will have some value for DP[i][j] (for subproblem, f(i,j)), Else DP[i][j] will contain the initialized value only.

因此，我們首先在DP [] []中查找它是否已解決。 如果已經解決，則DP [i] [j]會有一些值(對于子問題f(i，j) )，其他DP [i] [j]僅包含初始化值。

This is the trick here.

這是這里的把戲。

Below is the full CPP implementation for understanding memorization.

以下是用于理解記憶的完整CPP實施。

C++ Implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
int findmax(vector<int> arr, int in, int n, int* lastindex)
{
int max = INT_MIN;
for (int i = 0; i < n; i++) {
if (arr[i] > max && i != in) {
max = arr[i];
*lastindex = i;
}
}
return max;
}
int recurZigZag(vector<vector<int> > arr, int row, int col, int n, int** dp)
{
//memoization part
if (dp[row][col] != -1) //if already solved, no need to compute again
return dp[row][col];
if (row == n - 1) {
dp[row][col] = arr[row][col];
return arr[row][col];
}
int max = INT_MIN;
for (int k = 0; k < n; k++) {
if (k != col) {
int t = recurZigZag(arr, row + 1, k, n, dp);
if (max < t)
max = t;
}
}
dp[row][col] = std::max(dp[row][col], arr[row][col] + max); //store solution
return dp[row][col];
}
int main()
{
int t, n, item;
cout << "Enter test case:\n";
cin >> t;
for (int i = 0; i < t; i++) {
cout << "Input size of square matrix\n";
cin >> n;
vector<vector<int> > arr;
cout << "Input the square matrix\n";
for (int i = 0; i < n; i++) {
vector<int> inn;
for (int j = 0; j < n; j++) {
cin >> item;
inn.push_back(item);
}
arr.push_back(inn);
}
int** dp = (int**)(malloc(sizeof(int*) * n));
for (int i = 0; i < n; i++) {
dp[i] = (int*)(malloc(sizeof(int) * n));
for (int j = 0; j < n; j++)
dp[i][j] = -1;
}
int mymax = INT_MIN;
for (int i = 0; i < n; i++) {
int p = recurZigZag(arr, 0, i, n, dp);
if (p > mymax)
mymax = p;
}
cout << "Maximum zigzag sum: " << mymax << endl;
}
return 0;
}

Output

輸出量

Enter test case:
2
Input size of square matrix 
3
Input the square matrix  
3 8 2  
4 8 5  
6 9 7  
Maximum zigzag sum: 22
Input size of square matrix 
3
Input the square matrix  
3 2 1  
10 8 5 
6 6 4  
Maximum zigzag sum: 18

翻譯自: https://www.includehelp.com/icp/largest-zigzag-sequence.aspx

ue 抗鋸齒 渲染序列失靈