本文主要是介绍面试题77：二维数组递减路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个二维数组，从左下方元素开始，找出最长一条递减路径，路径只能往右方和上方移动。
例如：
1 3 2
5 4 6
7 9 8
则最长路径为：7->5->4->3->2
思路：
回溯思想。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;void FindPathCore(int row,int col,vector<vector<int>> num, vector<vector<int>> &re,vector<int>&path)
{int size1 = num.size();int size2 = num[0].size();if (row >= size1 || col >= size2 || row<0 || col<0) return;path.push_back(num[row][col]);if (row == 0 && col == size2 - 1) re.push_back(path);if (col<size2 - 1 && ((row == 0 && num[row][col] > num[row][col + 1]) || (num[row][col] > num[row][col + 1])))FindPathCore(row, col + 1, num, re, path);else if (row>0 && ((col == size2 - 1 && num[row][col] > num[row - 1][col]) || (num[row][col] > num[row - 1][col])))FindPathCore(row - 1, col, num, re, path);else re.push_back(path);path.pop_back();
}int GetLargest(vector<vector<int>> re)
{if (re.size() == 0) return 0;unsigned int max = re[0].size();for (unsigned int i = 1; i < re.size(); i++){if (re[i].size() > max) max = re[i].size();}return max;
}int FindPath(vector<vector<int>> num)
{int size1 = num.size();if (size1 == 0) return 0;int size2 = num[0].size();vector<vector<int>> re;vector<int> path;for (int i = size1-1; i >= 0; i--){for (int j = 0; j < size2; j++){if (i == 0 && j == 0) FindPathCore(i, j, num, re, path);else if (i == 0 && num[i][j] >= num[i][j - 1]) FindPathCore(i, j, num, re, path);else if (j == 0 && num[i][j] >= num[i - 1][j]) FindPathCore(i, j, num, re, path);else if (num[i][j] >= num[i][j - 1] && num[i][j] >= num[i - 1][j]) FindPathCore(i, j, num, re, path);}}return GetLargest(re);
}int main(){int N = 5;vector<vector<int>> num(N, vector<int>(N, 0));for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){num[i][j] = i + j;}}num[2][1] = 1;num[2][2] = 0;num[2][3] = -1;num[2][4] = -2;num[1][4] = -3;for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){cout << num[i][j] << " ";}cout << endl;}cout << FindPath(num) << endl;return 0;
}
这篇关于面试题77：二维数组递减路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
