动态规划理解

动态规划

基本思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解乘若干个子问题，先求子问题，

然后从这些子问题的解得到原问题的解。动态规划中分解得到的子问题往往不是相互独立的。

若用分治法，则分解的子问题数目会太多，导致时间复杂度过高。在动态规划中我们将已解决

子问题的答案保存在一个表，在需要时在找到以求的答案，这样可以避免大量的重复计算，这

便是动态规划的基本思想。

步骤：

（1）找出最优解的性质，并刻画其结构特征

（2）递归定义最优质

（3）以自底向上的方式计算出最优值

（4）根据计算最优值时得到的信息构造最优解

习题递归方程

//单调递增最长子序列
//ans[i]表示以元素a[i]为结尾的最长递增子序列的值
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++)
        {
            if(a[i]>a[j]&&ans[i]<ans[j]+1)
                ans[i]=ans[j]+1;
            res=max(res,ans[i]);
        }
　　　　cout<<res<<endl;   

//租用游艇问题    
//dp[i]表示从1到i花费的最少钱

    for(int i=2;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            cin>>temp;
            if(dp[i]+temp<dp[j])
                dp[j]=dp[i]+temp;
        }
    }
    cout<<dp[n]<<endl; 

结对编程情况

结对编程主要在上机实践时交流比较多，代码之间的风格也存在一定的不同。不同的题目队友有自己的想法

能够多多学习，希望能取长补短更进一步。