动态规划(c++) ->通过

思路链接 https://blog.csdn.net/StubbornAccepted/article/details/72383701

c++复现：

#include<iostream>

using namespace std;

int cost(int** arr, int a, int b) {
    
    int** dp = new int*[a];
    for(int i= 0;i < b; i++) dp[i] = new int[b];
    dp[0][0] = arr[0][0];
    for(int i = 1 ;i < a ; i++){
        dp[i][0] = dp[i-1][0] + arr[i][0];
    }
    for(int j = 1 ;j < b ; j++){
        dp[0][j] = dp[0][j-1] + arr[0][j];
    }
    
    for(int i = 1;i < a; i++){
        for( int j = 1;j < b; j++){
            dp[i][j] = min(dp[i-1][j] , dp[i][j-1]) + arr[i][j];
        }
    }
    //cout << arr[a][b] << endl;
    return dp[a-1][b-1];
}

int main() {
    int a, b, num;
    int** arr;
    cin >> a >> b;
    arr = new int* [a];
    for (int i = 0; i < a; i++) {
        arr[i] = new int[b];
    }

    for (int i = 0; i < a; i++) {
        for (int j = 0; j < b; j++) {
            cin >> arr[i][j];
        }
    }
    
    cout << cost(arr, a, b) << endl;
    return 0;
}

贪心法(C++)->未通过

测试案例一通过，提交案例一不能通过，贪心法的局限性。

#include<iostream>

using namespace std;

int cost(int** arr, int a, int b) {

    a = a - 1;
    b = b - 1;
    for (int x = 0, y = 0; x <= a && y <= b; ) {
        if (x != a && y != b) {
            //cout << a << b << endl;
            if (arr[x + 1][y] < arr[x][y + 1]) {
                arr[x + 1][y] = arr[x + 1][y] + arr[x][y];
                x = x + 1;
            }
            else {
                arr[x][y + 1] = arr[x][y + 1] + arr[x][y];
                y = y + 1;
            }
        }

        else{
            if(x == a){
                arr[x][y+1] = arr[x][y+1] + arr[x][y];
                y = y + 1;
            }else{
                arr[x+1][y] = arr[x+1][y] + arr[x][y];
                x = x + 1;
            }
        }

    }
    //cout << arr[a][b] << endl;
    return arr[a][b];
}

int main() {
    int a, b, num;
    int** arr;
    cin >> a >> b;
    arr = new int* [a];
    for (int i = 0; i < a; i++) {
        arr[i] = new int[b];
    }

    for (int i = 0; i < a; i++) {
        for (int j = 0; j < b; j++) {
            cin >> arr[i][j];
        }
    }
    
    cout << cost(arr, a, b) << endl;
    return 0;
}