jingchi店面2

jignchi店面2

一道dp问题，一条

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

想出来。欸
求大米

used DP to solve it .

1. #include<vector>
   
2. #include<iostream>
   
3. 
   
4. using namespace std;
   
5. 
   
6. double cal(vector<double>& p, int k){
   
7.    // p means green light.
   
8.    int n = p.size();
   
9.    vector< vector<double> > dp(n+1, vector<double>(k+1, 0.0) );
   
10.    dp[0][0] = 1.0;
    
11.    for( int i= 1; i<n+1; i++ ) dp[i][0] = (1.0-p[i-1])*dp[i-1][0];
    
12.    
    
13.    for(int i= 1; i<n+1; i++){
    
14.        for(int j= 1; j<=i && j<k+1; j++){
    
15.            dp[i][j] = dp[i-1][j-1]*p[i-1] + dp[i-1][j]*(1.0-p[i-1]);
    
16.         }
    
17.     }
    
18. 
    
19. 
    
20.     return dp[n][k];
    
21. }
    
22. 
    
23. 
    
24. int main(){
    
25.     vector<double> p = {0.3, 0.3, 0.3}; //p means green light
    
26.     int n = 1;
    
27. 
    
28.     double res = cal(p, n);
    
29.     cout << res << endl;
    
30.     return 0;
    
31. }

复制代码

补充内容 (2018-11-5 13:27):
the probability of each light does not have to be the same, just used same numbers for easier verification.

这题为什么要用dp 不是数学问题么 求教～

pr1234567 发表于 2018-11-5 13:19
used DP to solve it .

[mw_shl_code=cpp,true]#include

请问 这个dp代表的是什么？谢谢！

bensvage 发表于 2019/02/24 17:56:28


请问 这个dp代表的是什么？谢谢！

Dynamic programming

请问楼主面的时候可以用java吗