golang刷leetcode 技巧（34）n个骰子的点数

func twoSum(n int) []float64 {
    var r []float64
    dp:=make([][]int,n+1)
    for i:=0;i<n+1;i++{
        dp[i]=make([]int,n*6+1)
    }

    s:=pow(6,n)

    //1  1...6
    //2  2...12 
    for i:=1;i<=6;i++{
        dp[1][i]=1
    }

    for i:=2;i<=n;i++{
        for j:=i;j<=i*6;j++{
            for k:=1;k<=6;k++{
                if j>k{
                   
                    dp[i][j]+=dp[i-1][j-k]
                     fmt.Println( dp[i][j],":",i,j,"=>",i-1,j-k)
                }
            }
            if j==i*6{
            //    dp[i][j]=1
            }
            
        }
    }
    for  j:=n;j<=n*6;j++{
        r=append(r,float64(dp[n][j])/float64(s))
    }
     fmt.Println(dp[n][n:n*6+1])
    fmt.Println(dp,s)
    return r

}


func pow(x,y int)int{
    r:=1
    for i:=0;i<y;i++{
       r*=x
    }
    return r
}


/**
解题思路
dp[i][j]表示当n=i时，和为j出现的排列情况总数；
状态转移方程：dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]+dp[i-1][j-5]+dp[i-1][j-6];
初始条件：dp[1][1]=dp[1][2]=dp[1][3]=dp[1][4]=dp[1][5]=dp[1][6]=1;

代码
class Solution {
public:
    vector<double> twoSum(int n) {
        vector<vector<int>>dp(n+1,vector<int>(6*n+1,0));
        double num=pow(6,n);
        vector<double>res(5*n+1,1/(double)6);
        //初始状态
        for(int i=1;i<=6;i++)dp[1][i]=1;
        for(int i=2;i<=n;i++){      //从2到n计算dp
            for(int j=i;j<=i*6;j++){  //表示当n=i时候的点数和取值从i到6i
                for(int k=1;k<=6;k++){  //dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]+dp[i-1][j-5]+dp[i-1][j-6];
                    if(j-k>0)dp[i][j]+=dp[i-1][j-k]; //第i个骰子点数一定比i-1个骰子点数大
                    if(i==n)res[j-i]=dp[i][j]/num;
              }
            }
        }        
        return res;
    }
};
*/