动态规划基础总结

自下而上先求解子问题，从子问题的解得到原问题的解

可分为四个步骤

1.确定状态

2.列出转移方程

3.获得边界条件

4.按一定顺序计算最优解

自下而上递推，maxSum[i][j]代表第i行j列到底部的最大和，maxSum[1][1]为所求最大和

#include   
#include  
#define maxn 1001  
using namespace std; 
 
int dp[maxn][maxn];   
int n;  
int maxSum[maxn][maxn]; 

int main()
{    
	int i,j;    
	cin >> n;    
	for(i=1;i<=n;i++)   
		for(j=1;j<=i;j++)        
			cin >> dp[i][j];   
	for( int i = 1;i <= n; ++ i )     
		maxSum[n][i] = dp[n][i];   
	for( int i = n-1; i>= 1;  --i )     
		for( int j = 1; j <= i; ++j )         
			maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + dp[i][j];    
	cout << maxSum[1][1] << endl;  
} 

记dp[i][j]为前i道菜花费j元钱的办法数，递推求出dp[n][m]

如果：第i道菜价格等于j，dp[i][j]=dp[i-1][j]+1

           第i道菜价格小于j，dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i]]

           第i道菜价格大于j，dp[i][j] = dp[i - 1][j]

#include
using namespace std;

int a[105];
int dp[105][10005];


int main()
{
	int n,m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= m; j++)
		{
			if (j == a[i])
				dp[i][j] = dp[i - 1][j] + 1;
			if (j > a[i])
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i]];
			if (j < a[i])
				dp[i][j] = dp[i - 1][j];
		}
	cout << dp[n][m];
	return 0;
}

 f[i][j]代表当前路径数

#include
using namespace std;

long long  f[22][22];//棋盘
int ctrl[22][22];//马的控制点
int x, y, hx, hy;
int d[9][2] = { {0,0},{1,2},{1,- 2},{-1,2}, {-1,-2},{2,1},
	          {2,-1},{-2,1},{-2,-1} };//马控制范围

int main()
{
	cin >>x >> y >> hx >> hy;

	for (int i = 0; i < 9; i++)
	{
		int tmpx = hx + d[i][0], tmpy = hy + d[i][1];
		if (tmpx >= 0 && tmpx <= x && tmpy >= 0 && tmpy <= y)
			ctrl[tmpx][tmpy] = 1;
	}

	f[0][0] = 1 - ctrl[0][0];

	for (int i = 0; i <=x; i++)
		for (int j = 0; j <= y; j++)
		{
			if (ctrl[i][j]) continue;
			if (i != 0)f[i][j] += f[i - 1][j];
			if (j != 0)f[i][j] += f[i][j - 1];
		}
	cout << f[x][y]<