// ConsoleApplication2.cpp : 定義控制臺應(yīng)用程序的入口點。
//
//臺階問題：有一座高度是10級臺階的樓梯，從下往上走，每跨一步只能向上1級或者2級臺階。要求用程序來求出一共有多少種走法。
#include "stdafx.h"
#include <iostream>
using namespace std;
int getResultByDP(int n)//自底向上的問題解法
{
	if (n<1)
	{
		return 0;
	}
	if (n==1)
	{
		return 1;
	}
	if (n==2)
	{
		return 2;
	}
	int a = 1;//從兩個遞歸基開始
	int b = 2;
	int temp = 0;
	for (int i = 3; i < n + 1; i++)
	{
		temp = a + b;
		a = b;
		b = temp;
	}
	return temp;
}
int _tmain(int argc, _TCHAR* argv[])
{
	cout << getResultByDP(10);
	system("pause");
	return 0;
}

//給定一個矩陣m，從左上角開始每次只能向右走或者向下走，最后達到右下角的位置，路徑中所有數(shù)字累加起來就是路徑和，返回所有路徑的最小路徑和，如果給定的m如下，那么路徑1,3,1,0,6,1,0就是最小路徑和，返回12.
#include "stdafx.h"
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int const x_length=5, y_length=5;
int m[x_length][y_length] = {
	0, 0, 0, 0, 0,
	0, 1, 3, 5, 9,
	0, 8, 1, 3, 5,
	0, 5, 0, 6, 1,
	0, 8, 8, 4, 0
};
int minDis() //m二級指針（可以是一個二維數(shù)組）
{
	int dp[4 + 1][4 + 1];
	//---------初始化邊界條件-----------------
	for (size_t i = 0; i < x_length; i++)
	{
		dp[i][0] = 0;
	}
	for (size_t j = 0; j < y_length; j++)
	{
		dp[0][j] = 0;
	}
	//-------------------------------------------
	for (size_t i = 1; i < x_length; i++)
	{
		for (size_t j= 1; j < y_length; j++)
		{
			if (i == 1)
			{
				dp[i][j] = dp[i][j - 1] + m[i][j];
			}
			else if (j == 1)
			{
				dp[i][j] = dp[i - 1][j] + m[i][j];
			}
			else
			{
				int temp1 = dp[i - 1][j] + m[i][j];
				int temp2 = dp[i][j - 1] + m[i][j];
				dp[i][j] = min(temp1, temp2);
			}			
		}
	}
	return dp[x_length - 1][y_length - 1];
}
int _tmain(int argc, _TCHAR* argv[])
{
	cout << "最右下角的最短路徑為：" << minDis();
	system("pause");
	return 0;
}

//給定數(shù)組arr，返回arr的最長遞增子序列的長度，比如arr=[2,1,5,3,6,4,8,9,7]，最長遞增子序列為[1,3,4,8,9]返回其長度為5.
#include "stdafx.h"
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dp[5] = {};
int _tmain(int argc, _TCHAR* argv[])
{
 int arr[5] = { 2, 4, 5, 3, 1 };
 dp[0] = 1;
 const int oo = 0;
 for (int i = 1; i<5; i++){
  int _max = oo;
  for (int j = 0; j<i; j++)
   if (dp[j]>_max && arr[i]>arr[j])
    _max = dp[j];
  dp[i] = _max + 1;
 }
 int maxlist = 0;
 for (int i = 0; i < 5; i++)
  if (dp[i] > maxlist)
   maxlist = dp[i];
 cout << maxlist << endl;
 system("pause");
 return 0;
}

//輸入為兩個長度不為零的字符串，輸出這兩個字符串的最大公共子序列
#include "stdafx.h"
#include <string>
#include <iostream>
#ifndef MAX
#define MAX(X,Y) ((X>=Y)? X:Y)
#endif
using namespace std;
int **Lcs_length(string X, string Y, int **B)
{
 int x_len = X.length();
 int y_len = Y.length();
 int **C = new int *[x_len + 1];
 for (int i = 0; i <= x_len; i++)
 {
  C[i] = new int[y_len + 1];        //定義一個存放最優(yōu)解的值的表；
 }
 for (int i = 0; i <= x_len; i++)
 {
  C[i][0] = 0;
  B[i][0] = -2;                     //-2表示沒有方向
 }
 for (int j = 0; j <= y_len; j++)
 {
  C[0][j] = 0;
  B[0][j] = -2;
 }
 for (int i = 1; i <= x_len; i++)
 {
  for (int j = 1; j <= y_len; j++)
  {
 
   if (X[i - 1] == Y[j - 1])
   {
    C[i][j] = C[i - 1][j - 1] + 1;
 
    B[i][j] = 0;             //0表示斜向左上
   }
   else
   {
    if (C[i - 1][j] >= C[i][j - 1])
    {
     C[i][j] = C[i - 1][j];
     B[i][j] = -1;       //-1表示豎直向上；
    }
    else
    {
     C[i][j] = C[i][j - 1];
     B[i][j] = 1;        //1表示橫向左
    }
   }
 
  }
 }
 return C;
}
 
void OutPutLCS(int **B, string X, int str1_len, int str2_len)
{
 if (str1_len == 0 || str2_len == 0)
 {
  return;
 }
 if (B[str1_len][str2_len] == 0)   //箭頭斜向左上
 {
  OutPutLCS(B, X, str1_len - 1, str2_len - 1);
  cout << X[str1_len - 1] << endl;
 }
 else if (B[str1_len][str2_len] == -1)
 {
  OutPutLCS(B, X, str1_len - 1, str2_len);
 }
 else
 {
  OutPutLCS(B, X, str1_len, str2_len - 1);
 }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
 string X = "ABCBDAB";
 string Y = "BDCABA";
 
 int x_len = X.length();
 int y_len = Y.length();
 
 int **C;//定義一個二維數(shù)組
 
 int **B = new int *[x_len + 1];
 for (int i = 0; i <= x_len; i++)
 {
  B[i] = new int[y_len + 1];
 }
 C = Lcs_length(X, Y, B);
 for (int i = 0; i <= x_len; i++)
 {
  for (int j = 0; j <= y_len; j++)
  {
   cout << C[i][j] << " ";
  }
  cout << endl;
 }
 cout << endl;
 for (int i = 0; i <= x_len; i++)
 {
  for (int j = 0; j <= y_len; j++)
  {
   cout << B[i][j] << " ";
  }
  cout << endl;
 }
 OutPutLCS(B, X, x_len, y_len);//構(gòu)造最優(yōu)解
 system("pause");
 return 0;
}