【算法】动态规划算法

#include<iostream>
using namespace std;

int WalkCount(int n)
{
	//可以一次走一阶台阶，也可以一次走两阶台阶
	if (n < 0)
	{
		return  0;
	}
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}
	else {
		return WalkCount(n-1)+WalkCount(n-2);
	}
}
int main(void)
{
	cout << WalkCount(45) << endl;
	return 0;
}

long long  WalkCount(int n)
{

	long long  ret = 0;
	if (n <= 0)
	{
		return 0;
	}
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}
	long long * value = new long long[n + 1];//索引从0开始
	value[0] = 0;
	value[1] = 1;
	value[2] = 2;

	for (int i = 3; i <= n; i++)
	{
		value[i] = value[i - 1] + value[i - 2];
	}

	ret = value[n];
	delete value;
	return ret;
}

//传进来的是绳子的长度
int CutRope(int n)
{
	int result = 0;
	if (n <= 1)
	{
		return 0;
	}
	if (n == 2)
	{
		return 2;
	}
	if (n == 3)
	{
		return 3;
	}
	//动态开辟数组
	int* temp = new int[n + 1];//数组索引从0开始
	//绳子多长(n多大),对应分割的最大乘积就存在数组对应下标所指向的值temp[n]
	temp[0] = 0;
	temp[1] = 0;
	temp[2] = 2;
	temp[3] = 3;
	/*
	我们不需要去考虑到底要分割成多少段求出来的乘积才是最大的，
	每次分割成都两段，这两段的乘积最大值已经在之前求出来并且存到了temp中对应的位置上了，
	我们只需要对比这几种分割(分成两段的不同情况，这两段最大的乘积都是多少)选出最大的，
	放到该长度n，在temp数组中的位置即可。
	例： 4 可以分为1 3，2 2 ，3 1 
	1、2、3分成的乘积最大值，在之前已经求出来了，最需要分成这两种的乘积即可。
	3 4 3 最大为 4 ，存进temp[4] = 4;
	
	*/
	for (int i = 4; i <= 4; i++)
	{
		int max = 0;//保存当前长度乘积最大的。
		//循环计算出最大的
		for (int j = 1; j <= i / 2; j++)
		{
			if (max < temp[j] * temp[i - j])
			{
				max = temp[j] * temp[i - j];
			}
		}
		temp[n] = max;
	}
	result = temp[n];
	delete temp;
	return  result;
}