大盗阿福（线性DP）

本文主要是介绍大盗阿福（线性DP），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 这题是关于线性DP
• 这题大意是：阿福偷东西，如果偷一家商店，则相邻两家不能偷，否则报警系统出发，w [ i ] 为偷能得到的价值。
• 那么我们就首先应该想如何写出递归式

1. 我们首先假设阿福偷第 i 个商店，则第 i + 1 和 i - 1 个商店不能偷
2. 我们就设二维 f 数组 ，f [ i ] [ 1 ] 为可以偷，f [ i ] [ 0 ] 不偷，我们可以画图理解一下递推式如何来。如图：
   

   由图我们可以明白不偷第 i - 1 个商店则可以选择偷下一个商店或不偷；偷第 i - 1个商店则只能不偷下一个

3. 所以我们可以写出递推式：

          f(i)(0) = max( f(i - 1)(0) ,  f( i - 1)(1) + w[i]).

          f(i)(1) = f(i-1)(0).  

       4. 初始化 f数组

          f(1)(0) =0         f(1)(1) = w[1]. 

       贴贴代码......    

#include<bits/stdc++.h>
using namespace std;
int n;
int t;
int f[10010][3];
int w[10001];
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>w[i];
        f[1][0]=0;f[1][1]=w[1];
        for(int i=2;i<=n;i++){
            f[i][0]=max(f[i-1][1],f[i-1][0]);
            f[i][1]=f[i-1][0]+w[i];
        }
        cout<<max(f[n][1],f[n][0]);
    }
    return 0;
}

最后想一想有什么优化的麻？ 当然有，把二维数组化为一维数组，就成了。

代码奉上

#include<bits/stdc++.h>
using namespace std;
int n,t;
int w[10001];
int f[10001];
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>w[i];
        f[0]=0;f[1]=w[1];
        for(int i=2;i<=n;i++){
            f[i]=max(f[i-2]+w[i],f[i-1]);
        }
        cout<<f[n]<<endl;
    }
    return 0;
}

这篇关于大盗阿福（线性DP）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！