【算法——二维动态规划】

64. 最小路径和

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

int dfs(int i,int j,vector<vector<int>>nums)  //右下到左上dfs
{
	if (i == 0 && j == 0)
		return nums[0][0];
	int up = INT_MAX;
	int left = INT_MAX;
	if (i - 1 >= 0)
		up = dfs(i - 1, j, nums);
	if (j - 1 >= 0)
		left = dfs(i, j - 1, nums);
	return nums[i][j] + min(up, left);
}


int dfs(vector<vector<int>>nums,int i,int j)    //左上到右下dfs
{
	if (i == nums.size() - 1 && j == nums[0].size() - 1)
		return nums[i][j];
	int x = INT_MAX ,y = INT_MAX ;
	if (i + 1 < nums.size())
		x = dfs(nums, i + 1, j);
	if (j + 1 < nums[0].size())
		y = dfs(nums, i, j + 1);

	return nums[i][j] + min(x, y);
}

 
void dp1(vector<vector<int>>nums)    //左上到右下dp
{
	int n = nums.size();
	int m = nums[0].size();
	vector<vector<int>>dp(n, vector<int>(m));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (i == 0 && j == 0)
				dp[i][j] = nums[0][0];
			else
			{
				if (j == 0)
					dp[i][j] = nums[i][j] + dp[i - 1][j];
				if (i == 0)
					dp[i][j] = nums[i][j] + dp[i][j - 1];
				if (i != 0 && j != 0)
					dp[i][j] = nums[i][j] + min(dp[i][j - 1], dp[i - 1][j]);
			}
			
		}
	}

	for (auto i : dp)
	{
		for (auto j : i)
			cout << j << " ";
		cout << endl;
	}
}

void dp2(vector<vector<int>>nums)   //右下到左上dp
{

	int n = nums.size();
	int m = nums[0].size();
	vector<vector<int>>dp(n, vector<int>(m));

	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = m - 1; j >= 0; j--)
		{
			if (i == n - 1 && j == m - 1)
				dp[i][j] = nums[n-1][m-1];
			else 
			{
				if (j == m-1)
					dp[i][j] = nums[i][j] + dp[i + 1][j];
				if (i == n-1)
					dp[i][j] = nums[i][j] + dp[i][j + 1];
				if (i != n-1 && j != m-1)
					dp[i][j] = nums[i][j] + min(dp[i][j + 1], dp[i + 1][j]);
			}

		}

	}

	for (auto i : dp)
	{
		for (auto j : i)
			cout << j << " ";
		cout << endl;
	}
}

void dp3(vector<vector<int>>nums)   //空间压缩
{
	vector<int>dp(nums[0].size());
	dp[0] = nums[0][0];
	for (int i = 1; i < nums[0].size(); i++)
		dp[i] = nums[0][i] + dp[i - 1];

	for (int i = 1; i < nums.size();i++)
	{
		dp[0] += nums[i][0];
		for (int j = 1; j < nums[0].size(); j++)
		{
			dp[j] = nums[i][j] + min(dp[j - 1], dp[j]);
		}
	}
	for (auto i : dp)
		cout << i << " ";

}


int main()
{
	vector<vector<int>>nums = {
		{1,2,3},
		{4,5,6},
		{7,8,9}
	};
	cout << dfs(nums.size() - 1, nums[0].size() - 1, nums) << endl << endl;

	vector<vector<int>>dp(nums.size() + 1, vector<int>(nums[0].size() + 1));
	dp1(nums);
	cout << endl;
	dp2(nums);
	cout << endl;
	dp3(nums); 


	return 0;
}

79. 单词搜索

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

bool dfs(vector<vector<char>>board,int i,int j,string word,int k)
{
	if (k == word.size()) return 1;

	if (i < 0 || i == board.size() || j < 0 || j == board[0].size() || board[i][j] != word[k]) return 0;

	char str = board[i][j];
	board[i][j] = 0;
	bool ans = dfs(board, i + 1, j, word, k + 1) 
		|| dfs(board, i - 1, j, word, k + 1) 
		|| dfs(board, i, j + 1, word, k + 1) 
		|| dfs(board, i, j - 1, word, k + 1);
	board[i][j] = str;
	return ans;
}


int main()
{
	vector<vector<char>>board;
	string word;
	for (int i = 0; i < board.size(); i++)
	{
		for (int j = 0; j < board[0].size(); j++)
		{
			if (dfs(board, i, j, word, 0))
				return 1;
		}
	}
	

	return 0;
}