Re: [閒聊] 每日LeetCode
※ 引述 《Rushia (みけねこ的鼻屎)》 之銘言：
:
: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/description
: 1155. Number of Dice Rolls With Target Sum
: 給你三個數字 n、k、target，n 表示丟幾次骰子，k 表示骰子有幾面（1~k點），target
: 表示目標點數，求出丟 n 次骰子後共有幾種可能點數和為 target，因為數字很大所以
: 要取模運算。
:
: 思路：
: 1.如果骰子全骰到最大的和小於target，不用算可以直接返回 0。
: 2.定義 f(n, m) 表示使用 n 顆骰子和為 m 的方法數，很明顯的 f(1, 1:k) 都是 1
: ，而當我們投一顆新骰子時每個點數會產生 k 個新的和，舉例來說當骰子數為2時
: 可能是 1+1, 1+2, 1+3, ..., 1+k，所以我們遍歷所有之前不為0（可以骰出來的數字）
: 的點數加上當前的點數做 n 輪之後檢查 f(n, target) 即可。
我的想法是直接像畫圖一樣
弄一個陣列出來
假設有k=6 n=3
然後target 是9
我的陣列會長這樣
目前總和 0 1 2 3 4 5 6 7 8 9
零個骰子 1 0 0 0 0 0 0 0 0 0
一個骰子 0 1 1 1 1 1 1 0 0 0
兩個骰子 0 0 1 2 3 4 5 6 5 4
三個骰子
就是算當前的骰子是第幾個
假設是3
他要到哪裡不重要 假設是6
有什麼數字
假設現在看的是1這面
那他到6的方法數就 加上左上格子的算法
假設看的是2這面
那他到6的方法數就 加上左左上格的算法
假設3這面
加左左左上的算法
把所有骰子跟他們面數弄一次
就可以了捏
主要是這樣
捏
今天這題好有趣喔
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume cal
ler calls free().
*/
int** construct2DArray(int* original, int originalSize, int m, int n, int* retur
nSize, int** returnColumnSizes)
{
int max = 0;
max = m*n;
int* no = malloc(sizeof(int) * 0);
if(originalSize != max)
{
*returnSize = 0;
*returnColumnSizes = malloc(sizeof(int) * 0);
return no;
}
*returnSize = m;
*returnColumnSizes = malloc(sizeof(int) * m);
for(int i = 0 ; i < m ; i ++)
{
(*returnColumnSizes)[i] = n;
}
int** map = malloc(sizeof(int*) * m);
for(int i = 0 ; i < m ; i ++)
{
map[i] = malloc(sizeof(int) * n);
}
int c = 0;
printf("hi");
for(int i = 0 ; i < m; i ++)
{
for(int j = 0 ; j < n ; j ++)
{
map[i][j] = original[c] ;
c ++;
}
}
return map;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.57.64 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1703610050.A.A78.html
推
12/27 01:12,
1年前
, 1F
12/27 01:12, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 585 之 719 篇)：