LeetCode 1444

2024-01-10 01:35| 来源: 网络整理| 查看: 265

题目描述

1444. 切披萨的方案数

解法一：DP（C++）

详细参考雪融之时. 的解

统计可能数，一来挺容易行到用动态规划

状态：我们每次切完都是接着处理剩下的部分，那么可以记 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] 表示可能的切法， ( i , j ) (i, j) (i,j)表示剩余披萨的左上角为，当前披萨被切分为 k k k块

转移方程： d p [ x ] [ y ] [ k + 1 ] = d p [ i ] [ j ] [ k ] i f ( 切分的两部分都有苹果 ) dp[x][y][k+1] = dp[i][j][k]\ \ if(切分的两部分都有苹果) dp[x][y][k+1]=dp[i][j][k] if(切分的两部分都有苹果)，其中记原来的左上角为 ( i , j ) (i, j) (i,j)，切分后新的左上角为 ( x , y ) (x, y) (x,y)

对于是横切还是竖切，就通过穷举了

最后讲一下，怎么判断切分的部分上是否有苹果？这个思想还是挺有趣的

n u m s [ i ] [ j ] nums[i][j] nums[i][j] 表示以 ( 0 , 0 ) (0, 0) (0,0) 为左上角， ( i , j ) (i, j) (i,j)为右下角的矩形区域的苹果数，那么任一区域（左上角为 ( s r , s c ) (sr, sc) (sr,sc)，右下角为 ( e r , e c ) (er,ec) (er,ec)）包含的苹果数就可以通过 n u m s [ e r ] [ e c ] − n u m s [ s r − 1 ] [ e c ] − n u m s [ e r ] [ s c − 1 ] + n u m s [ s r − 1 ] [ s c − 1 ] nums[er][ec] - nums[sr-1][ec]-nums[er][sc-1]+nums[sr-1][sc-1] nums[er][ec]−nums[sr−1][ec]−nums[er][sc−1]+nums[sr−1][sc−1] 求得

typedef long long ll; class Solution { public: int ways(vector& pizza, int k) { const ll MOD = 1e9+7; int row = pizza.size(), col = pizza[0].length(); vector nums(row, vector(col, 0)); if(pizza[0][0]=='A') nums[0][0] = 1; for(int i=1;i for(int j=0;j if(hasapple(nums, i, j, z-1, col-1)&&hasapple(nums, z, j, row-1, col-1)) { dp[z][j][x] += dp[i][j][x-1]; dp[z][j][x] %= MOD; } } for(int z=j+1;z dp[i][z][x] += dp[i][j][x-1]; dp[i][z][x] %= MOD; } } } } } ll ans= 0; for(int i=0;i(row, col):(0,0)} for _ in range(k)] first_apple = [[None] * col for _ in range(row)] def FisrtApple(r, c): '''定义对first_apple的访问方法，避免越界''' return (row, col) if r>= row or c >= col else first_apple[r][c] for r in range(row)[::-1]: for c in range(col)[::-1]: first_apple[r][c] = (r, c) if pizza[r][c] == 'A' else tuple(map(min, zip(FisrtApple(r+1, c), FisrtApple(r, c+1)))) if first_apple[r][c] != (row, col): table[0][first_apple[r][c]] = (1, ) def dfs(r, c, remain): if (r, c) in table[remain]: return table[remain][r, c] nr, nc = FisrtApple(r+1, c) across = (dfs(nr, nc, remain)[0] + (nr-r)*sum(dfs(nr, nc, remain - 1))) % MOD nr, nc = FisrtApple(r, c+1) vertical = (dfs(nr, nc, remain)[1] + (nc-c)*sum(dfs(nr, nc, remain - 1))) % MOD table[remain][r, c] = (across, vertical) return (across, vertical) r0, c0 = FisrtApple(0, 0) return sum(dfs(r0, c0, k-1)

【本文地址】

LeetCode 1444

LeetCode 1444

今日新闻

推荐新闻