题目描述:
我们正在玩一个猜数游戏,游戏规则如下:
我从 1 到 n 之间选择一个数字,你来猜我选了哪个数字。
每次你猜错了,我都会告诉你,我选的数字比你的大了或者小了。
然而,当你猜了数字 x 并且猜错了的时候,你需要支付金额为 x 的现金。直到你猜到我选的数字,你才算赢得了这个游戏。
示例:
n = 10, 我选择了8.
第一轮: 你猜我选择的数字是5,我会告诉你,我的数字更大一些,然后你需要支付5块。
第二轮: 你猜是7,我告诉你,我的数字更大一些,你支付7块。
第三轮: 你猜是9,我告诉你,我的数字更小一些,你支付9块。
游戏结束。8 就是我选的数字。
你最终要支付 5 + 7 + 9 = 21 块钱。
给定 n ≥ 1,计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
参考代码位置
主要思路:
(1)理解dp[ i ][ j ]含义:依次以从 i 到 j 的字符作为分割点,赢得游戏所使用的最少钱的值;
(2)则对于位于 i 和 j 之间的字符 k 为选择点时,此时所用的最少钱的值为 k+max(dp[ i ][ k-1 ],dp[ k+1 ] [ j ]),则对i和j之间的每个可能的字符进行遍历,求出最小值;
(3)对于两端的值,既k=i 时,dp[i][j]=min(dp[i][j],i+dp[i+1][j]);,k=j时,dp[i][j]=min(dp[i][j],j+dp[i][j-1]);
(4)为了使上述的状态方程可以计算,需要初始化dp[ i ] [ i ]=0,且整体的求值过程是从左下到右上进行;
(5)最后输出dp[1][n],既整个字符串在此要求下的最少钱的值;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40class Solution { public: int getMoneyAmount(int n) { if(n==1) return 0; //定义矩阵 // int dp[n+1][n+1]; //初始化 vector<vector<int>>dp(n+1,vector<int>(n+1,INT_MAX)); //初始化“” //for(int i=0;i<=n;i++){ // for(int j=i+1;j<=n;j++){ // dp[i][j]=INT_MAX; // } // } //定义基础值dp[i][i] //初始化 for(int i=0;i<=n;i++){ dp[i][i]=0; } //按列来,从第2列开始 for(int j=2;j<=n;j++){ //按行来,从下往上 for(int i=j-1;i>=1;i--){ //算除了两端的每一个分割点 for(int k=i+1;k<=j-1;k++){ dp[i][j]=min(k+max(dp[i][k-1],dp[k+1][j]),dp[i][j]); } //算两端 dp[i][j]=min(dp[i][j],i+dp[i+1][j]); dp[i][j]=min(dp[i][j],j+dp[i][j-1]); } } return dp[1][n]; } };
最后
以上就是玩命饼干最近收集整理的关于375 猜数字大小 II-动态规划的全部内容,更多相关375内容请搜索靠谱客的其他文章。
发表评论 取消回复