第十四周学习总结

这周着重学习动态规划，看了看博客并自己刷了一些题目，总结一下动态规划的做题思路。

首先设计状态，然后写出状态转移方程，设定初始状态，之后进行状态转移并求出最终的解。

其中最让我头疼的还是设计状态和写出状态转移方程，有好多题目状态不明显，根本就想不到。

1.P1255 数楼梯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这是一道最基础简单的动态规划问题，是我第一道写的，状态找不到，看了题解才搞清楚

由于到第i级台阶的方法只有两种，从第i-1级到的和第i-2级到的，所以

dp[i]=dp[i-1]+dp[i-2]          dp[i]是到第i级所能走的方法数

#include
using namespace std;
int main()
{
    long long int dp[5005],n;
    dp[0]= {1};
    dp[1]= {1};
    cin>>n;
    for(int i=2; i<=n; i++)
        dp[i]=dp[i-1]+dp[i-2];
    cout<

#include
using namespace std;
int main()
{
    long long int dp[30][30];
    int n,m,a,b;
    cin>>n>>m>>a>>b;
    if(b!=0)
        for(int i=0; i<=n; i++)
            dp[i][0]=1;
    else
    {
        for(int i=0; i

#include
using namespace std;
int max(int a,int b)
{
    return a>b?a:b;
}
int rob(int *nums,int n)
{
    int i;
    int dp[110];
    dp[0]=nums[0];
    for(i=0; i