MOOC 攔截飛彈（動規基礎）

題目連結在此，拿需

思路：基礎動規題目，主要就是看出狀态轉移方程，然而，本水筆還是寫不出動規程式，先寫了個遞歸壓壓驚。感覺還是要拓展思路，總是想着dp[][]把自己往死裡逼。。。不懂自己怎麼回事。

遞歸中出現的錯誤是，把max_num置為0了，至少為1。

代碼如下：

#include<iostream>
 
int numbers[30][30]={0};
int height[30] ={0};
using namespace std;
int solves(int start,int k);
inline int mymax(int a,int b)
{
	return a>b?a:b;
};
int main(void)
{
	int k,max_num = 0;
	cin>>k;
	for(int i=0;i<k;i++)
	{
		cin>>height[i];
	}
	
	for(int j = 0;j<k;j++)
	{
		max_num=mymax(max_num,solves(j,k));
	}
	
	cout<<max_num<<endl;
	
	return 0;
} 

int solves(int start,int k)
{
	int max_num = 1;
	if(start==(k-1))
	{
		return 1;
	}
	for(int j = start+1;j<k;j++)
	{
		if(height[start]>=height[j])
		{
			 max_num=mymax(max_num,1+solves(j,k));
		}	
	}
	return max_num;
}
           

至于動規程式，引自： 點選打開連結。

其中給出更詳細的思路，與解答，并附上了最優代碼（我絕不承認我看不懂）。