文章目錄
- 62. 不同路徑
- 算法原理
- 代碼實現
- 63. 不同路徑 II
- 算法原理
- 代碼實現
- LCR 166. 珠寶的最高價值
- 算法原理
- 代碼實現
62. 不同路徑
題目鏈接：62. 不同路徑
算法原理
-
狀態表示：
dp[i,j]：以[i, j]位置為結尾，走到[i, j]位置有多少種方式 -
狀態轉移方程：
根據最近的一步劃分問題
只能從左側和上側到達該位置，所以兩種情況
這里是一步，而不是一種方法，比如說
A->B->C->[i,j]，這是這個方法里面的一步，所以不加1所以
dp[i][j] = dp[i-1][j] + dp[i][j-1] -
初始化：
保證填表不越界，這里采用添加虛擬節點在虛擬節點當中
[0,1]位置填1，其他位置填0，即可按照我們的要求初始化完畢，因為是根據上和左的值相加
-
填表順序：
大方向是從上往下填每一行，每一行從左往右 -
返回值：
dp[m][n]
代碼實現
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m+1, vector<int>(n+1));dp[0][1] = 1;for(int i = 1; i <=m; i++){for(int j = 1; j <=n; j++){dp[i][j] = dp[i][j-1] + dp[i-1][j];}} return dp[m][n];}
};
63. 不同路徑 II
題目鏈接：63. 不同路徑 II
這題就是上一題的升級版，加入了“障礙物”（該位置不能走）
算法原理
-
狀態表示：
經驗+題目要求：dp[i][j]表示到達[i,j]位置時，一共有多少只方法 -
狀態轉移方程：
這里加入了判斷是否有“障礙物的情況”
有障礙物的情況下，我們的
dp[i][j]里面填的值是0，所以放些加就好了 -
初始化：
也是和上題類似，只不過這里的映射關系，需要注意一下，dp表里面要找到矩陣的對應位置，需要減1，即obstacleGrid[i-1][j-1] -
填表順序： 也和上一題一樣
-
返回值：
dp[m][n]
代碼實現
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid){int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1));dp[0][1] = 1;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){//映射關系需要減1if(obstacleGrid[i-1][j-1] == 0){dp[i][j] = dp[i-1][j] + dp[i][j-1];}}}return dp[m][n];}
};
LCR 166. 珠寶的最高價值
題目鏈接：LCR 166. 珠寶的最高價值
題目意思就是從左上角到右下角能獲取的最大值價值（每次只能向下或者向右走）
算法原理
- 狀態表示：
經驗+題目要求：dp[i][j]表示到達[i,j]位置時，此時能拿到的最大價值 - 狀態轉移方程：
根據最近的一步劃分問題
- 初始化：
保證填表不越界，這里也是采用虛擬節點，這個虛擬節點的值不影響，都設置為0，因為“珠寶”的價值，全部都是大于0的，我們取的是max - 填表順序： 從上到下填每行，每行從左往右
- 返回值：
dp[m][n]
代碼實現
class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {int m = frame.size();int n = frame[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1));for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){//注意下標的映射dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1];}}return dp[m][n];}
};
