劍指 Offer 46. 把數(shù)字翻譯成字符串
給定一個(gè)數(shù)字，我們按照如下規(guī)則把它翻譯為字符串：0 翻譯成 “a” ，1 翻譯成 “b”捍壤，……，11 翻譯成 “l(fā)”拂酣，……钓觉，25 翻譯成 “z”。一個(gè)數(shù)字可能有多個(gè)翻譯庄拇。請(qǐng)編程實(shí)現(xiàn)一個(gè)函數(shù)倍啥，用來計(jì)算一個(gè)數(shù)字有多少種不同的翻譯方法禾乘。
- 動(dòng)態(tài)規(guī)劃
class Solution {
public int translateNum(int num) {
String numStr = String.valueOf(num);
int len = numStr.length();
//dp[i]表示前i + 1位數(shù)字的翻譯方法
int[] dp = new int[len + 1];
//base case
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= len; i++){
//獲得第i-1位和第i位組合而成的數(shù)字
int temp = Integer.parseInt(numStr.substring(i - 2, i));
if(temp > 9 && temp < 26){
//若數(shù)字在[10,25]區(qū)間內(nèi)，則可以有兩種翻譯策略
dp[i] = dp[i - 1] + dp[i - 2];
}else{
dp[i] = dp[i - 1];
}
}
return dp[len];
}
}
劍指 Offer 47. 禮物的最大價(jià)值
在一個(gè) m*n 的棋盤的每一格都放有一個(gè)禮物逗栽，每個(gè)禮物都有一定的價(jià)值（價(jià)值大于 0）盖袭。你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動(dòng)一格彼宠、直到到達(dá)棋盤的右下角鳄虱。給定一個(gè)棋盤及其上面的禮物的價(jià)值，請(qǐng)計(jì)算你最多能拿到多少價(jià)值的禮物凭峡？
- 動(dòng)態(tài)規(guī)劃
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length;
if(m == 0 || grid[0].length == 0){
return 0;
}
int n = grid[0].length;
//dp[i][j]表示在grid[i][j]格子內(nèi)能拿到的禮物的最大價(jià)值
int[][] dp = new int[m][n];
int max = 0;
for(int i = 0 ; i < m; i++){
for(int j = 0; j < n; j++){
if(i == 0 && j == 0){
//左上角出發(fā)點(diǎn)
dp[i][j] = grid[i][j];
continue;
}
if(i == 0){
//第一行
dp[i][j] = dp[i][j - 1] + grid[i][j];
}else if(j == 0){
//第一列
dp[i][j] = dp[i - 1][j] + grid[i][j];
}else{
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
}
return dp[m - 1][n - 1];
}
}
