【B站】动态规划学习

https://www.bilibili.com/video/BV1ET4y1U7T6?p=6&spm_id_from=pageDriver

暴力递归到动态规划

//测试用例
#include <iostream>

using namespace std;
int** dp1 = nullptr;
int** dp2 = nullptr;
int way1(int N, int M, int K, int P);//暴力递归
int process1(int N, int M, int K, int P);//暴力递归过程
int way2(int N, int M, int K, int P);//暴力递归优化
int process1(int N, int M, int K, int P, int** dp);//暴力递归引入dp
int way3(int N, int M, int K, int P);//动态规划


int main()
{
	  N,M,K,P
	cout << way1(4, 2, 4, 4) << endl;
	cout << way2(4, 2, 4, 4) << endl;
	cout << way3(4, 2, 4, 4) << endl;

	for (int i = 0; i <= 4; i++)
	{
		delete[] dp1[i], dp2[i];
	}
	delete[] dp1, dp2;
	dp1 = dp2 = nullptr;
	return 0;
}

//N个位置，机器人在M位置上，必须走K步，最终来到P位置上
int way1(int N, int M, int K, int P)//暴力递归
{
	if (N < 2 || K < 1 || M<1 || M>N || P<1 || P>N)
	{
		return 0;
	}
	return process1(N, M, K, P);
}

int process1(int N, int M, int K, int P)
{
	if (K == 0)//已经不需要走
	{
		return M == P ? 1 : 0;
	}
	if (M == 1)//第一个位置，只能往下走
	{
		return process1(N, 2, K - 1, P);
	}
	else if (M == N)//最后的位置，只能往上走
	{
		return process1(N, N - 1, K - 1, P);
	}
	//中间位置上
	return process1(N, M + 1, K - 1, P) + process1(N, M - 1, K - 1, P);
}

int way2(int N, int M, int K, int P)
{
	if (N < 2 || K < 1 || M<1 || M>N || P<1 || P>N)
	{
		return 0;
	}
	int** dp = new int*[N + 1];
	for (int i = 0; i <= N; i++)
	{
		dp[i] = new int[K + 1];
		for (int j = 0; j <= K; j++)
		{
			dp[i][j] = -1;
		}
	}
	dp1 = dp;//释放内存用
	//dp就是缓存表
	//dp[M][K] == -1代表之前没算过;!= -1代表之前的算过
	 process1(N, M, K, P,dp);
	 //打印结果，方便验证
	 for (int i = 1; i <= N; i++)
	 {
		 for (int j = 0; j <= K; j++)
		 {
			 cout << dp[i][j] << "\t";
		 }
		 cout << endl;
	 }
	 return dp[M][K];
}

int process1(int N, int M, int K, int P, int** dp)
{
	if (dp[M][K] != -1)//之前算过
	{
		return dp[M][K];
	}
	//没算过，就去算答案
	int ans = 0;
	if (K == 0)
	{
		ans = M == P ? 1 : 0;
	}
	else if (M == 1)
	{
		ans = process1(N, 2, K - 1, P, dp);
	}
	else if (M == N)
	{
		ans = process1(N, N - 1, K - 1, P, dp);
	}
	else
	{
		ans = process1(N, M + 1, K - 1, P, dp) + process1(N, M- 1, K - 1, P, dp);
	}
	dp[M][K] = ans;
	return ans;
}


int way3(int N, int M, int K, int P)
{
	if (N < 2 || K < 1 || M<1 || M>N || P<1 || P>N)
	{
		return 0;
	}
	int** dp = new int* [N + 1];
	for (int i = 0; i <= N; i++)
	{
		dp[i] = new int[K + 1];
		memset(dp[i], 0, sizeof(dp[i]));
	}
	dp2 = dp;//释放内存用
	dp[P][0] = 1;//第一列的值
	for (int rest = 1; rest <= K; rest++)//数组大小为（N+1）*（K+1）,第一列只有目的（P，0）为1，其他为0
	{
		dp[1][rest] = dp[2][rest - 1];//第一行只依赖第二行
		for (int cur = 2; cur < N; cur++)
		{
			dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
		}
		dp[N][rest] = dp[N - 1][rest - 1];//最后一行只依赖前一行
	}
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= K; j++)
		{
			cout << dp[i][j] << "\t";
		}
		cout << endl;
	}
	return dp[M][K];
}