动态规划，按摩师，爬楼梯，最大子数组和,最长递增子序列

• • 按摩师
  • 爬楼梯
  • 最大子数组和
  • • 去掉动态规划数组
  • 最长递增子序列

int max(int a, int b)
{
	if (a >= b)
	{
		return a;
	}
	return b;
}
int rob(vectorar,int n)
{
	vectorbr(ar.size());
	int ma = ar[0];
	br[0] = ar[0];
	br[1] = max(ar[0], ar[1]);
	if (ma < br[2]) ma = br[2];
	for (int i = 2; i < ar.size(); ++i)
	{
		br[i] = max(ar[i] + br[i - 2], br[i - 1]);
		if (ma < br[i]) ma = br[i];
	}
	return ma;
}
int rob1(vectorar, int a,int n)
{
	if (n == 0) return ar[0];
	if (n == 1) return max(ar[0], ar[1]);
	return max(ar[n] + rob1(ar, a, n - 2), rob1(ar, a, n - 1));
}
int main()
{
	vectorbr = {2,1,4,5,3,1,1,3 };
	cout << rob(br,br.size()-1) << endl;
	cout << rob1(br, br[0], br.size()-1) << endl;
	return 0;

}

标识相应的下标，并且不用数组

int rob(vectorar,vector&s)
{
	vectorbr(ar.size());
	int pre= ar[0];
	int next=0;
	int maxv = 0;
	s[0] = 1;
	if (ar[0] > ar[1])
	{
		next = ar[0];
		s[1] = 0;
	}
	else
	{
		next = ar[1];
		s[1] = 1;
		s[0] = 0;
	}
	for (int i = 2; i < ar.size(); ++i)
	{
		 if((ar[i] + pre)
			 maxv =next;
			 s[i] = 0;
		 }
		 else
		 {
			 maxv = ar[i] + pre;
			 s[i] = 1;
			 s[i - 1] = 0;
		 }
		 pre = next;
		 next = maxv;
	}
	return maxv;
}

int main()
{
	vectorbr = {2,1,4,5,3,1,1,3};
	vectors(br.size());
	int num = rob(br, s);
	for (int i = 0; i < s.size(); ++i)
	{
		if (s[i] == 1)cout << i << endl;;
	}
	cout << endl << num << endl;
	return 0;

}

动态规划方程：f(n)=f(n-1)+f(n-2);斐波那契数列

int main()
{
	vectorar = { -2,1,-3,4,-1,2,1,-5,4 };
	vectorbr(ar.size());
	int max = ar[0];
	br[0] = ar[0];
	for (int i = 1; i < ar.size(); ++i)
	{
		if (br[i-1]+ar[i] >ar[i])
		{
		  br[i]= ar[i] + br[i-1];
		}
		else
		{
			br[i]= ar[i];
		}
		if (br[i]> max) max = br[i];
	}
	cout << max << endl;
	return 0;
}

int main()
{
	vectorar = { -2,1,-3,4,-1,2,1,-5,4 };
	int max = ar[0];
	int prev= ar[0];
	int val = 0;
	for (int i = 1; i < ar.size(); ++i)
	{
		if (prev+ar[i] >ar[i])
		{
		  val= ar[i] + prev;
		}
		else
		{
			val= ar[i];
		}
		if (val> max) max = val;
		prev = val;
	}
	cout << max << endl;
	return 0;
}

int main()
{
	vectorar = { 0,1,0,1,2,3 };
	vectorbr(ar.size(),1);
	int max = 0;
	for (int i = 0; i < ar.size(); ++i)
	{
		for (int j = 0; j < i; ++j)
		{
			if (ar[i] > ar[j])
			{
				if (br[i] < br[j] + 1)
				{
					br[i] = br[j] + 1;
				}
			}
		}
		if (max < br[i]) max = br[i];
	}
	cout << max << endl;
	return 0;
}