LeetCode 375 猜数字大小 II

本文主要是介绍LeetCode 375 猜数字大小 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

猜数字大小 II

题目

思路

矩阵链乘法

https://www.baidu.com/link?url=57aywD0Q6WTnl7XKbIHuE7lcWGXh50Vy3z1lItKlmdBVCmwKnGAabf1b8YFFijUxeTWEk-kwrJNcVhJuUksguHQoQSX28BhmhSYUIGt8Yi_&wd=&eqid=8c7298ba0003d066000000055dcc2a61

https://www.jianshu.com/p/a5e0ceab8292

代码

class Solution {
public:int getMoneyAmount(int n) {vector<vector<int> > dp(n+1,vector<int>(n+1,INT_MAX));for(int i=1;i<=n;i++) dp[i][i] = 0;for(int l=1;l<=n;l++){for(int i=1;i+l<=n;i++){int j=i+l;if(i==j-1){dp[i][j]=i;continue;}for(int k=i+1;k<j;k++){dp[i][j]=min(dp[i][j],max(dp[i][k-1],dp[k+1][j])+k);}}}return dp[1][n];}
};

这篇关于LeetCode 375 猜数字大小 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---